3 ms·
No, 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 actual
by ganafagol 6y ago
No, 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.