4 ms·

Nope. You ignore that the constant factor is removed (i.e. all factors but the one that is dominant for n going to infinite). More precisly, it tells how the r

Nope. You ignore that the constant factor is removed (i.e. all factors but the one that is dominant for n going to infinite). More precisly, it tells how the relative speed difference between 2 algorithms change when n goes to toward infinity. An O(n) will win over O(n^2), but the latter case might have a huge constant factor that makes it slower than the former for e.g. n <= million. And very often, n is smaller than a million.

edanm 16y ago
That's true in some cases, but in a lot of cases the difference does come out even when n is in the thousands/millions range
whimsy 16y ago
This is true for O(n) but not for o(n). f(n) is the class of O(g(n)) of g(n) if g(n) dominates f(n) for sufficiently large n. o(g(n)) strictly dominates f(n), though, no matter how small n is. Big O notation, or Landau notation, is not just O(g(n)). It's also o(), Ω(), ω() and Θ(). It's understood, though, that n is considered to usually be rather large - another name for this notation is, after all, "asymptotic notation." In any case that you're really worried about speed, you should probably be calculating the speed of your algorithm directly rather than using mere asymptotic generalizations. Aside: I can't think of any algorithms with huge constants like you described; in theory, you're correct, but in practice, the asymptotic generalizations apply for n <= 1000 or even often 100.