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:
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top