682 views
1 votes
1 votes
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)$?

1 Answer

1 votes
1 votes

it is stable sort. stability of bucket sort not dependent on what we are using to sort bucket. but time complexity dependent

Bucket sort is mainly useful when input is uniformly distributed over a range. When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, which is typically O(N^2) insertion sort.making bucket sort less optimal than O(n*log(n) comparison sorting like quick sort.

source

https://en.wikipedia.org/wiki/Bucket_sort

Related questions

1 votes
1 votes
1 answer
3
akash.dinkar12 asked Jun 28, 2019
758 views
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?