2 ms·
I agree its misleading. Another example is that despite being O(log n), B-trees or skip lists can be much faster than hash tables if your keys are naturally ord
by josephg 6y ago
I agree its misleading. Another example is that despite being O(log n), B-trees or skip lists can be much faster than hash tables if your keys are naturally ordered (and queried in order) because of memory caching.
> It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.
Yep - its common in practice but sloppy. Technically its not big-O anymore if you're doing that. Its big-theta notation. (Same thing, just T(n) instead of O(n)).
https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
- Tainnor 6y agoWhy is it sloppy? The question of whether you use O or Theta is just that the one gives an upper bound only, and the other one ensures a tight bound (usually many people write O, when they mean Theta, which is not wrong, but is also doesn't tell you as much; in the end, it's mostly clear what is intended though). That doesn't mean that you can't use either notation to refer to a worst-case or an average-case (given a suitably defined probability distribution) performance. To say "expected complexity for hash table lookup is O(1)" is neither wrong, nor sloppy.