You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.
If you think this isn't useful in practice, you're right! If you want to compare the actual speed of an algorithm, benchmark it. And once you've done enough of that, your intuition will guide you far better than big-O notation ever could.
Eg even the worst case input for a randomised QuickSort still has an expected runtime of O(n log n). (Where the expectation is averaged over the random choices, not over the input.)
This statement is imprecise. What is "worst case input" when speaking of "expected".
Mathematically, worst case doesn't mean a known worst case that works every time. As long as I have an input that the random algorithm has a chance of generating the worst case, it will be O(n^2).
From an adversarial standpoint: If I have information about the random algorithm and the seed, I can make exploit it.
So yes, even the randomized Quick Sort has worst case of O(n^2)
Randomised QuickSort as an algorithm doesn't have any random seed. It just uses pure randomness. (Specific implementations might use a pseudo-RNG.)
> This statement is imprecise. What is "worst case input" when speaking of "expected".
Oh, just the opposite! Speaking of 'expected' tells you exactly what worst-case to look for.
What I mean is that 'worst case input' by itself is not a-priori well-defined for randomised algorithms. Because you could eg have an input that worsens the 75%-ile runtime but improves the 25%-ile runtime.
By specifying eg 'expected', you make clear that you are talking about the worst case for the expected runtime.
> So yes, even the randomized Quick Sort has worst case of O(n^2)
The worst case over both input and random choices is O(n^2). The worst case over input for the expected running time is O(n log n).
Even more, for any input, even the worst case input, randomised quicksort has O(n log n) running time with 'very high probability', ie for any epsilon there's a big enough m and a constant c, so that with probability at least 1-epsilon, the running time of the worst case input of size n > m is smaller than c * n log n.
---
There's a different, but equivalent, way to analyse randomised algorithms that might be easier to digest for you, because it completely avoids having to directly talk about randomness:
Take your favourite deterministic machine model, say a Turing machine or a random access machine, and in addition to the normal input tape, give it access to an extra immutable one-sided 'random' tape that's pre-filled with binary symbols (0 or 1).
Everything is deterministic in this model.
An analysis of the expected runtime for the worst case input means that the adversary gets to prepare the input tape, but for the rest of the analysis we are analysing all possible contents of the 'random tape'.
For each possibility, there is one specific deterministic run. Talking about the expected (worst-case input) runtime just means that we are averaging over all possible 'random' tapes.
If we talk about the 95%-ile instead, that means that we are ordering all the runtimes for the different possibilities for the 'random tape' and taking the runtime of the 95%-ile. Still, everything is deterministic.
When you want to run this algorithm in practice, you sample from the space of possible contents of the 'random tape'. But crucially, the standard assumption is that you sample after your adversary has selected their input.
That standard assumption is in line with Kerckhoffs's principle in cryptography that the adversary knows your system, but that you are able to pick secret random keys at will.
This is not how worst-case complexity analysis works. Worst-case means worst-case, ie. the input is selected by an adversary with complete knowledge of your algorithm and initial memory; and there is no source of randomness other than the input itself.
And, yes, that's usually not applicable in practice. But worst-case complexity is a theoretical concept defined only on abstract machines (implicitly a Von Neumann-like machine here).
Instead, to do useful analysis on hash tables, you should use probability complexity analysis, which allows your algorithm access to a source of randomness the adversary doesn't have access to.
That gives you 'worst-case expected runtime'. That concept is useful for eg analysing QuickSort with randomised pivots.
You can also analysis worst-case input and eg 99.999%-ile on the random choices.
Worst-case complexity is usually defined on Turing Machines or Von Neumann machines. In these models, algorithms cannot make "random choices", they are deterministic.
If you want to use a different computation model, you have to explicitly define it.
I think this is well established practice, since there are a lot of interesting algorithms and data structures that have been widely studied and are probabilistic.
You can analyze the worst case on the input while at the same time doing probability theory on the random choices. And since you control the random choice, you can impose nearly any reasonable distribution you feel like. (You just have to 'pay' for the generation of the random bits. Economizing on the number of random bits involved is just as much an area of research as economizing on runtime or memory.)
Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.
> Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.
But isn't this how it works for a hash table? It was my understanding that the actual hash function is deterministic, so there are no random choices to make - the randomness comes from the inputs; on the other hand you do have some assumptions (maybe not strictly proven) about the collision frequency, which should allow you to get a handle on the input distribution, or am I wrong?
But that lead to easy denial of service attacks. So many languages, like eg Python, patched their hashmaps to use randomized hashes.
See eg https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703
We would compute hashes out of some objects to compare for equality and it turned out we sometimes had more collisions than expected (orders of magnitude more), but this wasn't really reproducible. That was when I found out that the hashing algorithm wasn't deterministic. (Of course, the underlying cause was that our hash code calculations were not good and we had to fix them.)
Probabilistic Turing machine are sufficiently standard and well known. They (or the random-access machine equivalent) are basically the implied context whenever you talk about randomized algorithm.
See https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...
Especially if you use a randomized implementation.
Without upgrading your server you have the potential for someone to run a DDOS attack against you.
if we sidestep that issue for one moment, it's still true that you have worst case O(n) and average O(1), though.
Array lookup operations are constant time. You don't need to grow an array while reading from it. Append operations in a vector are O(n) but amortized constant time.
Hash tables work the same way - they have amortized constant time when inserting, but they should have constant time for reads when using a good hash function.
That said, technically we still classify hash table reads and writes as O(n). Big-O notation defines an upper bound on time, not the average time. And the upper bound on hash table reads and writes is O(n) if you have a terrible hash function (or carefully crafted inputs).
This is not useful knowledge though, because hash tables are usually fast in practice. If you're trying to figure out how something performs in practice (like the "isVowel" function in the blog post), the tool to reach for is a benchmark. Guess how a benchmark result will come out before you see the result, and over time you'll build an intuition for these things.
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.
Or I think at least a randomised simplex that has expected polynomial runtime even on the worst case input.
No assumptions on the input necessary.
The expectation is over the choice of random bits created while running the algorithm.
> 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...
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.