Scatter n keys into b equal-width buckets, insertion-sort each bucket, and concatenate. If the keys are uniform over the range, the expected work inside the buckets is n(n/b − 1)/2, which is linear when b is about n. That expectation is over the input distribution, not over anything the algorithm does, so it stops being true exactly when the keys stop being uniform — and the algorithm cannot tell.
Core ideas
The hard idea is a distinction, and it is the reason this lesson sits four after randomised quicksort rather than next to the other linear-time sorts.
Randomised quicksort's 2(n+1)Hₙ − 4n averages over the pivots the algorithm draws, so it holds for every array. Bucket sort's linear bound averages over a distribution the input is assumed to follow, and the algorithm makes no random choices at all: run it twice on the same keys and it does exactly the same thing. An assumption about the data is a promise somebody else has to keep.
Scattering is one pass and concatenating is another, so the interesting term is the insertion sorts. A bucket holding m keys costs up to m(m − 1)/2 comparisons, and summing that over buckets with n/b keys each gives n(n/b − 1)/2 — zero when every bucket holds one key, and n(n − 1)/2 when one bucket holds all of them. The whole range of behaviour is in how the keys divide.
Nothing about the algorithm changes when you change the distribution; the same code runs. At 48 keys in 12 buckets a uniform draw measures 90 comparisons, keys clustered in a twentieth of the range measure 592, and keys confined to one bucket measure 582. Double n on the clustered family and the count goes from 140 at 24 keys to 592 at 48 to 2282 at 96: roughly four times the work for twice the keys, which is what a quadratic cost looks like when it is measured.
The material
Where the expected work comes from, what it assumes, and what the same algorithm costs when the assumption is false.
Bucket sort over a key range [0, U) with b buckets: place each key x into bucket ⌊bx/U⌋, sort each bucket with insertion sort, and concatenate the buckets in order. The buckets are equal in width; nothing makes them equal in occupancy.
The scatter is Θ(n) and the concatenation is Θ(n + b). Everything else is the insertion sorts, and their cost depends on the bucket sizes, which depend on the keys. So the analysis is not about the algorithm at all: it is about a random variable determined by where the keys fall.
With b = n the expected inner work is zero, which is the sense in which bucket sort is called linear: the remaining cost is the scatter and the concatenation. The lab evaluates the expression as an exact rational, because the point of printing it beside a measurement is that the two are different kinds of number and can be subtracted.
Twelve buckets throughout. A uniform draw fills them 4 4 9 2 3 0 3 4 3 1 8 7 and costs 90 comparisons against an expectation of 72. Keys clustered in a twentieth of the range put all 48 into one bucket and cost 592. Keys confined to the first bucket cost 582. All three outputs are sorted; only the cost moved, and the code did not.
The gap between 72 and 90 on the uniform draw is worth a sentence of its own, because it is the honest half of the lesson. 72 is an expectation over the distribution; 90 is one draw from it. The bucket sizes above are visibly uneven — one bucket empty, one holding nine — and that unevenness is what a uniform draw looks like at n = 48. A measurement above the expectation is not a refutation of it.
Put the two claims of this course in the same sentence and the difference is unmissable. Randomised quicksort: for every array, the average over the algorithm's pivots is 2(n+1)Hₙ − 4n. Bucket sort: for keys drawn uniformly, the average over the draw is n(n/b − 1)/2. The first quantifies over inputs and averages over coins the algorithm controls; the second averages over inputs and controls nothing.
That is why one of them survives a hostile input and the other does not. An adversary who picks the array cannot move randomised quicksort's expectation, because the expectation never mentioned the array. An adversary who picks the keys moves bucket sort's cost to Θ(n²) by putting them all in one bucket, and the lab ships exactly that input.
None of which makes bucket sort a bad algorithm. It makes its bound a conditional one, and the condition is checkable: where do the keys come from, and is the range they are spread over the range the buckets divide? Hash values, uniformly generated identifiers and quantised sensor readings often satisfy it. Prices, word lengths and timestamps of human activity usually do not.
One last discipline. The measured 582 on the one-bucket input is not the worst case; n(n − 1)/2 = 1128 is, and insertion sort only reaches it on a reversed bucket. The measured column is one input's cost and the proved column is about all of them, and this page keeps them apart on purpose.
Interactive
Change the distribution and nothing about the algorithm changes but its cost
Method
Every average-case bound has a hypothesis. Find it before you find the bound.
Over the algorithm's own random choices, or over a distribution the input is assumed to follow? Write the sentence out in full. If the answer is the second, the bound is a conditional statement and the condition belongs in every quotation of it.
n(n/b − 1)/2 at your n and b. At 48 keys over 12 buckets it is exactly 72. This is the number the measurement will be compared against, and having it first stops the measurement from becoming the claim.
90 against 72 on the uniform draw. A single draw is a sample of the distribution the expectation is over, so it moves when the seed moves. Watch it move.
Switch to the clustered keys and read the count: 592 for the same 48 keys through the same code. Then change n and check the growth. Roughly four times the work for twice the keys is quadratic behaviour on this family — measured, not proved.
“Linear if the keys are uniform over the bucketed range, quadratic in the worst case” is the whole claim. Θ(n) on its own is the misconception, and it is the one the lab's distribution control exists to break.
The bucket count, the key count and the code are identical in all three rows. Only where the keys fall is different, and the expectation in the second column is the same number throughout because it is computed from n and b alone.
The middle column is the only thing that changed, and it is not part of the algorithm. That is the entire content of “an average-case bound is a claim about the input”, and it is why the row for the clustered keys is the same code costing six and a half times as much.
Two figures are deliberately not equal to anything. 90 is not 72, because one draw is not an expectation. And 592 is not 1128, because the worst case needs the one full bucket to be in reverse order as well as full — the measured column is this input and the proved column is all of them.
For a faded rehearsal, keep the clustered keys and raise the bucket count from 12 to 32. The supplied first move is the prediction: the buckets are equal-width, and the keys occupy a twentieth of the range, so widening the bucket count divides that twentieth among at most two buckets. Say whether the cost falls by much, then check — and then say what bucket count would actually fix this input, and whether you could have known it without seeing the keys.
You should be able to derive n(n/b − 1)/2, evaluate it exactly at a given n and b, say what the expectation is over, produce an input that makes the algorithm quadratic, and explain why randomised quicksort's expectation is a different kind of claim.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.