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
Fungus deadly to AIDS patients found to grow on trees
Canola genome sequence reveals evolutionary 'love triangle'
Scientists uncover clues to role of magnetism in iron-based superconductors
I like Serena
#2
Aug27-11, 04:34 PM
HW Helper
I like Serena's Avatar
P: 6,187
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