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
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
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