Question

What is the worst case time complexity of bucket sort (k = number of buckets)?

(a) O(n + k)

(b) O(n.k)

(c) O(n^2)

(d) O(n log n)

The question was posed to me in a job interview.

I'd like to ask this question from Sorting topic in section Sorting of Data Structures & Algorithms II

Answer 1

Right option is (c) O(n^2)

For explanation: Time complexity of bucket sort is O(n^2) in the worst case. So if bucket sort does not get the inputs in the desired manner then it becomes very inefficient.