3 ms·

Big O only says something about n = Infinite. But n is never infinite in computer programs. Big O is a tool for making estimates, and like all other (such) to

Big O only says something about n = Infinite. But n is never infinite in computer programs. Big O is a tool for making estimates, and like all other (such) tools, you have to know its limitations to use it properly.

edanm 16y ago
"Big O only says something about n = Infinite." Err, no it doesn't. Big O is a tool for saying how quickly an algorithm runs based on the size of n, and it's usually used to measure real things, like what will happen when the filesystem has to handle 100,000 files, then 1,000,000, etc.
- silvestrov 16y ago
  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.
- baddox 16y ago
  That explanation is not right either (at least I don't find it intuitive). It's not about the size of n at all, but about how the running time changes when n changes.
baddox 16y ago
Actually, it's not meant for making estimates, it's meant to compare algorithms. You can't look at a single quadratic algorithm and try to estimate how long it will take to run on a certain input and certain hardware. That would be pointless, because any quadratic algorithm would result in exactly the same estimate.

edanm 16y ago

"Big O only says something about n = Infinite." Err, no it doesn't. Big O is a tool for saying how quickly an algorithm runs based on the size of n, and it's usually used to measure real things, like what will happen when the filesystem has to handle 100,000 files, then 1,000,000, etc.

silvestrov 16y ago
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.
baddox 16y ago
That explanation is not right either (at least I don't find it intuitive). It's not about the size of n at all, but about how the running time changes when n changes.

baddox 16y ago

Actually, it's not meant for making estimates, it's meant to compare algorithms. You can't look at a single quadratic algorithm and try to estimate how long it will take to run on a certain input and certain hardware. That would be pointless, because any quadratic algorithm would result in exactly the same estimate.