Register to reply

Computational complexity with an epsilon

by yavanna
Tags: complexity, computational, epsilon
Share this thread:
yavanna
#1
Aug22-11, 04:44 PM
P: 12
What does that mean when there's an [itex] \epsilon[/itex] in the complexity, such as
[itex] O(n^{2+\epsilon}) [/itex] for every [itex] \epsilon >0[/itex]
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
I like Serena
#2
Aug27-11, 04:34 PM
HW Helper
I like Serena's Avatar
P: 6,188
Quote Quote by yavanna View Post
What does that mean when there's an [itex] \epsilon[/itex] in the complexity, such as
[itex] O(n^{2+\epsilon}) [/itex] for every [itex] \epsilon >0[/itex]
Welcome to PF, yavanna!

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

Note that a complexity of [itex]O(n^{3})[/itex] as well as [itex]O(n^{4})[/itex] implies a complexity of [itex]O(n^{3})[/itex].


Register to reply

Related Discussions
Computational mathematics/computational physics and the video game industry Career Guidance 11
Energy and computational complexity of atomic interactions General Physics 0
How is computational complexity determined? General Math 1
How to find computational complexity? Programming & Computer Science 3
Computational complexity General Math 3