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, B, . . 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!