Master theorem for worst case quicksort

Question

I know how to calculate the master theorem and I managed to calculate it for best and average case. T(n) = 2T(n/2) + Theta(n)

The worst case equation is T(n) = T(n-1) + Theta(n) If I am correct a is 1, b is n/(n-1) and f(n) is n. But how do I choose the right case of the master theorem and get a worst-case time complexity of Theta(n^2)?

Thanks!

Answer 1

As @DavidEisenstat pointed out in the comments, the Master Theorem doesn’t apply to the recurrence you’ve come up with here.

To give some context as to why this is - the Master Theorem is specifically designed for the case where

• the number of subproblems is a constant, and
• the sizes of the subproblems decays geometrically.

In this case, that second requirement doesn’t hold, since your recurrence has the problem size decay linearly rather than geometrically.

You are correct, however, that the recurrence solves to Θ(n²). To see why, note that if you unroll the recurrence, you get that the cost is

Θ(n + (n-1) + (n-2) + ... + 2 + 1)

= Θ(n(n+1)/2)

= Θ(n²).

Hope this helps!