Re:Big O Notation – Explained as easily as possible
by bonzini on Saturday January 16, 2021 @03:38PM
(#25805292)
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.
[ Parent
| on HN ]
Re:Big O Notation – Explained as easily as possible
by ganafagol on Sunday January 17, 2021 @02:09AM
(#25808826)
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.
Re:Big O Notation – Explained as easily as possible
by bonzini on Sunday January 17, 2021 @04:51AM
(#25809485)
I 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.