1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Ah, the often skipped step! Good call! $\endgroup$ – Raphael Aug 27 '17 at 21:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "maximize this function subject to ∑|Bi|=n." This is essentially where I'm stuck. How do I proceed with maximising this? $\endgroup$ – Indo Ubt Aug 27 '17 at 21:59
  • $\begingroup$ @IndoUbt Normalize the sums by replacing $B_i$ with $B_i / n$, and moving $c$ outside of the sum. Do you see why the sum of squares is $\leq 1$? Hint: Use that the sum of the $B_i$ is $=1$ then. $\endgroup$ – Raphael Aug 28 '17 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.