What about partition algorithim?

The Gateway to Computer Science Excellence

+1 vote

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

0 votes

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)**

52,345 questions

60,517 answers

201,937 comments

95,368 users