Big O Notation – Explained as easily as possible

Re:Big O Notation – Explained as easily as possible by tshaddox on Saturday January 16, 2021 @02:52PM (#25804912)

There can be appropriate levels of imprecision. Arguably all communication necessarily requires that. This is only a problem if it leads to an unnoticed miscommunication. For example, I suspect most of the time when an engineers refers to an algorithm as being in O(n^2) they intend to preclude the possibility that the algorithm is not in O(n).

[ Parent | on HN ]

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.

[ Parent | on HN ]

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.

[ Parent | on HN ]