Recurrence for the Worst-Case Running Time of Quicksort

Question

Assume we constructed 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(1) + theta(n)

Worst case occurs when the subarrays are completely unbalanced. There is 1 element in one subarray and (n-1) elements in the other subarray. theta(n) because it takes running time n to find the pivot.

Am I doing this correctly?

Solution 1

Your recurrence is mostly correct, but you don't actually have two recursive calls made. In the worst-case for quicksort, the pivot will be the largest or smallest element in the array, so you'll recur on one giant array of size n - 1. The other subarray has length 0, so no recursive calls are made. To top everything off, the total work done is Θ(n) per level, so the recurrence relation would more appropriately be

T(n) = T(n - 1) + Θ(n)

This in turn then solves to Θ(n²).

Hope this helps!

Solution 2

you cannot observe, because according to my research T(N)= T(N-K)+T(K-1)+n we cannot observe exact value until we have value of k,