3 ms·
There can be appropriate levels of imprecision. Arguably all communication necessarily requires that. This is only a problem if it leads to an unnoticed miscomm
by 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 agoUsually "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 agoNo, 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 agoI 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]