2 ms·
Big-O notation refers to the worst case runtime of an algorithm. I have no idea where this misconception comes from. Big-O notation is a type of bound on a fu
by btilly 12y ago
Big-O notation refers to the worst case runtime of an algorithm.
I have no idea where this misconception comes from.
Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc.
The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.
- wzsddtc 12y agothat's not 100% true as well, you got omega and theta and others as well for the other cases. Edit: See http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on http://stackoverflow.com/questions/471199/what-is-the-differ...
- jholman 12y agobtilly's comment is exactly correct (though obviously not a complete explanation of everything). The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly. I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".