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).
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.
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.
Re:Big O Notation – Explained as easily as possible
by OakNinja on Sunday January 17, 2021 @02:51AM
(#25809015)
Your comment reminded me of this SO answer: https://stackoverflow.com/a/185576/1502563
/* This is O(scary), but seems quick enough in practice. */
Whether I like it or not, by now big o notation has fallen into the category of "folklore" that working engineers use and abuse informally without being very precise about it.
It's like the "proof by engineers induction": if some statement P(n) is true for P(0), P(1) and P(2), then P(n) is true for all n \in Z. :-)
Similarly if an engineer states that algorithm has a runtime of O(f(n)) that should probably be read as "as n grows very large (whatever that means) the runtime approximates (whatever that means) some bound (below, above, whatever) f(n). yolo.".
But people should at least be _aware_ that they are being imprecise about it.
If I read a blog post or StackOverflow post or whatever and I see big-theta notation I know that the person is probably precise with her definition. If I see big-o then it may be correct, or accidentally correct (happens often due to the nature of the definition) or mistaken.