News for hackers. Stuff that matters.
Re:Big O Notation – Explained as easily as possible by Edmond on Saturday January 16, 2021 @12:44PM (#25803808)
Agreed.

The use of "Big O Notation" itself as a way of referring to algorithmic complexity seems like a misnomer, considering that the topic is about analysis rather than the notation used to express the results of such analysis.

Unfortunately academic textbooks have terrible "UX", so students end up dealing with confusing presentation of topics, hence we're stuck with labels such as "Big O Notation".

Re:Big O Notation – Explained as easily as possible by bjeds on Saturday January 16, 2021 @01:04PM (#25803961)
I hear you.

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.

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. */