Explain why the worst-case running time for bucket sort is $\theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n lg n)$?
The bucket sort assumes the input distribution is uniformly distributed over $0 \leq n \lt 1$. But if the input is not unifornly distributed and if all elements fall in to a single bucket we will get n elements in a single bucket to sort n elements insertion sort needs $\theta(n^2)$. If we replace the sorting algorith by merge sort we will get $O(n log n )$ as the worst-case running time.
No comments:
Post a Comment