3 ms·
Usually "average" or worst case" O(n^2) means it's really big O, while "best case" or "always" O(n log n) means big Theta.
by bonzini 6y ago
Usually "average" or worst case" O(n^2) means it's really big O, while "best case" or "always" O(n log n) means big Theta.
- ganafagol 6y agoNo, that's the opposite of what parent wrote. If an engineer mentions "this makes our functions run in O(n^2)" they mean either average or worst case and actually mean theta. The interesting fact they want to express is not the upper bound but the lower bound.
- bonzini 6y agoI mean you say "best case O(n)" if the best case is Theta(n), even though the algorithm may be quadratic on average. You don't say the best case is O(n^2) if the best case is Theta(n log n) even though technically that would be correct.