281 views
0 votes
0 votes
Bucket Sort:

Didn't get how the complexity is O(n^2) from cormen.

1. As we take n as input, it might be the case that many numbers maps to same bucket. So n(per bucket one)*n/k(list in same bucket if distributed uniformly) = n^2.

2. Worst case all elements can map to same bucket. As we are maintaining linked list, adding all these node will take time = 1+2+3+4.....+n=n(n-1)/2= O(n^2).

Plz correct me.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
mb14 asked Jul 6, 2022
278 views
Iterative functions:f(n)= n/lognc=2What is f*(n) ?How to solve this question?