3 ms·

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

by Edmond 6y ago

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".

bjeds 6y ago
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.
- tshaddox 6y ago
  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).
  - bonzini 6y ago
    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.
    - 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 ago
        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.
  - deleted 6y ago
    [deleted]
- OakNinja 6y ago
  Your comment reminded me of this SO answer: https://stackoverflow.com/a/185576/1502563 https://stackoverflow.com/a/185576/1502563 /* This is O(scary), but seems quick enough in practice. */

by Edmond 6y ago

bjeds 6y ago

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.

tshaddox 6y ago
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).
- bonzini 6y ago
  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.
  - 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 ago
      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.
- deleted 6y ago
  [deleted]
OakNinja 6y ago
Your comment reminded me of this SO answer: https://stackoverflow.com/a/185576/1502563 https://stackoverflow.com/a/185576/1502563 /* This is O(scary), but seems quick enough in practice. */