No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time
Without upgrading your server you have the potential for someone to run a DDOS attack against you.
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.