4 ms·

Because you've simplified it to the point of being incorrect. First, you've confused big-O, which is an upper bound, with big-theta, which is a strict bound. Bu

Because you've simplified it to the point of being incorrect. First, you've confused big-O, which is an upper bound, with big-theta, which is a strict bound. But leaving that aside, big-O also drops constant factors, and your explanation doesn't. Also, it ignores finitely many 'irregularities', if I have a loop that normally runs n^2 times, except when n=17, 30, or 483, in which case it runs 10 billion times, that's still O(n^2). [That's actually implied by it ignoring constant factors, since you could just crank up the constant to 10 billion/17^2]. Finally, big-O notation describes arbitrary function growth, not just the runtime of some operation when applied to a list. It's used a lot in numerical analysis where you can show that some function can be approximated by, say, x - x^3/6 + x^5/120 + O(x^7).

twelvechairs 13y ago
Thanks for the detail - self taught so I'll defer and try to take on board (also written quickly - I'm sure doing no help to my annoyance that sparked the response - the single minded and to me complex approach of most of these explanations - which I'm sure you'll agree many of which make the same mistakes I have) one question though - do you have a source for this 'irregularities' bit? I've never seen that mentioned before at all and a Google hasn't helped. doesn't seem to fit with 'upper bound' and 'worst case'. [edit: also still not sure how you say im confusing for theta. that's what 'the largest number of times it might' was for.]
- velis_vel 13y ago
  If you look at the Wikipedia article on big-O notation, it says that f(x) = O(g(x)) if and only if there exists some M > 0 and x_0 such that |f(x)| < M|g(x)| for all x > x_0. The x_0 is what lets you ignore early irregularities; without it, you couldn't say that sin(x) + 1 is O(x) since there's obviously no M such that sin(0) + 1 < M * 0. You're right about the theta thing, my mistake.

twelvechairs 13y ago

Thanks for the detail - self taught so I'll defer and try to take on board (also written quickly - I'm sure doing no help to my annoyance that sparked the response - the single minded and to me complex approach of most of these explanations - which I'm sure you'll agree many of which make the same mistakes I have) one question though - do you have a source for this 'irregularities' bit? I've never seen that mentioned before at all and a Google hasn't helped. doesn't seem to fit with 'upper bound' and 'worst case'. [edit: also still not sure how you say im confusing for theta. that's what 'the largest number of times it might' was for.]

velis_vel 13y ago
If you look at the Wikipedia article on big-O notation, it says that f(x) = O(g(x)) if and only if there exists some M > 0 and x_0 such that |f(x)| < M|g(x)| for all x > x_0. The x_0 is what lets you ignore early irregularities; without it, you couldn't say that sin(x) + 1 is O(x) since there's obviously no M such that sin(0) + 1 < M * 0. You're right about the theta thing, my mistake.