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 discover RNA modifications in some unexpected places
Scientists discover tropical tree microbiome in Panama
'Squid skin' metamaterials project yields vivid color display
I like Serena
#2
Aug27-11, 04:34 PM
HW Helper
I like Serena's Avatar
P: 6,189
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