Proof of bucket sort worst case being all elements in one bucket

Question

By bucket sort I mean on dividing numbers between 0 and 1 into $n$ buckets and performing insertion sort on all the buckets.

1| n ← length [A]
2| For i = 1 to n do
3|     Insert A[i] into list B[nA[i]]
4| For i = 0 to n-1 do
5|     Sort list B with Insertion sort
6| Concatenate the lists B[0], B[1], . . B[n-1] together in order.

The time taking task is lines 4 and 5, which on uniform distribution takes $\Theta(n)$ time. So the worst case, by intuition, I can say is $\Theta(n^2)$ when all the elements fall into one bucket (standard insertion sort on $n$ elements).

But how can I prove that the worst case for this algorithm is when I take all elements in one bucket? Bucket sort worst case stuff I've seen online directly say that the worst case is when we have all elements in that one bucket. But how can I prove this in the first place? Thanks!

Answer 1

For an upper bound on the worst-case cost, it's sufficient to show that it can't be worse. Assuming that insertion sort takes $\leq cn^2$ steps on $n$ elements, consider the sum

$\qquad\displaystyle \sum_{i=1}^n c |B_i|^2$;

it is an upper bound on the cost of sorting all the buckets. For an upper bound on the worst case for bucket sort, maximize this function subject to $\sum |B_i| = n$ (and add the remaining cost, which is $O(n)$ for all inputs).

For a lower bound on the worst-case cost, we have to find an infinite class of actual inputs and show that their cost behaves as claimed. $[0, \dots, 0]$ serves to show an $\Omega(n^2)$ lower bound, as you note.