Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computational complexity with an epsilon

  1. Aug 22, 2011 #1
    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]
  2. jcsd
  3. Aug 27, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Welcome to PF, yavanna! :smile:

    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].
    Last edited: Aug 27, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook