+1 vote
179 views

In Randomized Quick sort, Can we have partitioning algorithm that never gives worst case as $O(n^2)$  for every input?

retagged | 179 views

Randomized Quick sort worst case is o(n^2).

suppose we take a pivot element and it is divided(partitioning) the array in two sub array . like one array have 0 element and other array have n-1 element then recurrence relation become

• T(n)=T(n-1)+o(n).
• time complexity=o(n^2)

edited
0