43 views

Doubt: Is it really possible to write recurrence relation of for quick sort like it is given in

the solution? if yes, then

Please explain that how can one find the value of k in quick sort’s recurrence relation

T(n)= T(n-k)+T(k-1)+cn in order to get the given recurrence relation in solution.

closed with the note: Doubt Cleared

closed | 43 views
+1
In the worst case, the pivot divides the list into 2 parts which are length 0 and length n-1 respectively.

In general, it is which you mentioned, but in worst case k=1 and here they mentioned choosing pivot itself takes O(n^2).