News for hackers. Stuff that matters.
Re:Plain english explanation of Big O by silvestrov on Friday July 16, 2010 @04:58PM (#1522540)
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.

Re:Plain english explanation of Big O by whimsy on Saturday July 17, 2010 @05:46AM (#1523565)
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.

Re:Plain english explanation of Big O by edanm on Saturday July 17, 2010 @04:55AM (#1523523)
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