Question

What is recurrence relation for worst case of quicksort?

Answer 1

Answer:

Assume we construcred a quicksort and the pivot value takes linear time find the recurrence for worst-case running time.

My answer : T(n)=T(n-1)+T(n)+theta(n).

Worst case occur when the subarrays are completely unbalance .There is element in one subarray and n-1 elements in the other subarray.

Theta n because it takes running time n to find the pivot.

Hope it helps you✌✌✌