Computational complexity with an epsilon

AI Thread Summary
The presence of an epsilon (ε) in complexity notation like O(n^{2+ε}) indicates that the algorithm's complexity is strictly greater than O(n²) for any ε > 0, but still less than O(n^{2.1}) for small values of ε. This notation suggests that while the complexity grows faster than quadratic time, it does not reach cubic time complexity. Additionally, complexities such as O(n³) or O(n⁴) would still fall under the broader classification of O(n³), highlighting the hierarchical nature of big O notation in describing algorithm efficiency.
yavanna
Messages
10
Reaction score
0
What does that mean when there's an \epsilon in the complexity, such as
O(n^{2+\epsilon}) for every \epsilon >0
 
Technology news on Phys.org
yavanna said:
What does that mean when there's an \epsilon in the complexity, such as
O(n^{2+\epsilon}) for every \epsilon >0

Welcome to PF, yavanna! :smile:

I would tend to take it very literally.
It says the complexity is greater than O(n^{2}).
But it is less than for instance O(n^{2.1}).

Note that a complexity of O(n^{3}) as well as O(n^{4}) implies a complexity of O(n^{3}).
 
Last edited:
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Back
Top