Comment by ecstrema | Hacker News Reader

Comment by ecstrema | Hacker News Reader

Maybe someone could clarify something for me here:

o(n) seems like a stronger statement to me than O(n), since all o(n) algorithms are O(n), but the reverse is not true.

Also if o(n) applies to all n, however small, whereas O(n) applies only when n -> inf,

(From the Wikipedia page example: 2n = O(n) but 2n != o(n))

Then doesn’t that means this algorithm should be applicable to even small n’s? Then it would be the opposite of a galactic algorithm, as someone above suggested, wouldn’t it?

Or am I missing something?

Little o is still an asymptotic statement: it doesn’t have to apply for small n. A definition of f(n) = o(g(n)) is something like

   lim (n -> infinity) f(n)/g(n) = 0

Or, in other words, for sufficiently large n, g grows faster than f.

For instance, this function is o(n), because 1e1000/n goes to 0 as n grows.

   f(n) = 10**n if n < 1000 else 1e1000

(Pseudo-Python for a piecewise function that grows exponentially to 10**1000 at n = 1000 and then remains constant after that.)

If the complexity of an algorithm is 3↑↑64*n^0.999, the algorithm is o(n) but can safely be said to be galactic.

* Ps, if memory serves me correct, 3↑↑64 is Graham's number.

Reply on news.ycombinator.com