CODEWITHSUNDEEP
algorithmmathquicksortrecurrence
Jonathan Lam
Jonathan Lam

Reputation: 185

Recurrence for the Worst-Case Running Time of Quicksort

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?

Upvotes: 3

Views: 34794

Answers (3)

SanjaySingh
SanjaySingh

Reputation: 1857

T(n) = T(an/(a+b)) + T(bn/(a+b)) + n

Where a/(a+b) and b/(a+b) are fractions of array under consideration

Upvotes: 0

Ali
Ali

Reputation: 11

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,

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372784

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 Θ(n2).

Hope this helps!

Upvotes: 3

Related Questions