Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.)


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: