3 ms·
You're right about the lookup being constant and insertions not, I didn't think it through well enough before posting. :) But I disagree about the O notation.
by Tainnor 6y ago
You're right about the lookup being constant and insertions not, I didn't think it through well enough before posting. :)
But I disagree about the O notation. The O notation is just a mathematical notation, it defines certain classes of functions. It can be used for many different things, worst-case complexity is one, but not the only one. It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.
People do look at expected complexity for probabilistic algorithms and data structures and they are useful. The idea that "O notation is not useful and you should perform benchmarks" should also be taken with a grain of salt, you don't always have time to perform benchmarks (and for good benchmarks, you also have to make some assumptions about the data, in particular when it comes to probabilistic data structures), while you can just read up on O notation for common algorithms (and do a quick in-your-head calculation for custom algorithms, e.g. three nested loops, then it's probably O(n^3), not always of course) and use that at least as a very useful first-order approximation.
But you're right that it's more complex: one of the best examples of this is that the simplex algorithm for linear optimisation is not known to be polynomial (in fact, I think for every possible variant of the algorithm that has so far been proposed, we know that it can degenerate to exponential time with bad inputs), but somehow that doesn't appear to be an issue in practice - it is my understanding that nobody fully understands why not. There are proven polynomial algorithms for linear optimisation, but they are more complicated and therefore less often used.
- eru 6y agoI think they have recently found polynomial simplex algorithms. Or I think at least a randomised simplex that has expected polynomial runtime even on the worst case input.
- Tainnor 6y agoThis is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
- eru 6y agoI just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....
- Tainnor 6y agothanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, and not a truly worst-case polynomial algorithm - as opposed to e.g. the ellipsoid method which is actually worst-case polynomial.
- eru 6y agoAs far as I understand it's runs in expected polynomial time regardless of input. No assumptions on the input necessary. The expectation is over the choice of random bits created while running the algorithm.
- josephg 6y agoI 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.