in Algorithms
661 views
1 vote
1 vote
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)$?
in Algorithms
661 views

1 Answer

1 vote
1 vote

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