Doubt

Question

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

Answer 1

 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)

Comments

What about partition algorithim?

---

Partition will always take o(n) in worst case.