time-complexityrecurrencedivide-and-conquermaster-theorem

Solving recurrence of divide and conquer using master theorem


Can T(n) = 3T(n/2) + c T(1)=0, solved using master theorem? If yes, I am struggling on understand master theorem now, could someone tell me which case it falls to and why.


Solution

  • There are different possible approaches for the master theorem. I like the one proposed by Cormen et al. in their book Introduction to Algorithms.

    1. If f(n) = O(n^(logb(a-e))) for some constant e>0, then T(n) = Θ(n^(logb(a)))
    2. If f(n) = Θ(n^(logb(a))), then T(n) = Θ(n^(logb(a)) . lg n)
    3. If f(n) = Ω(n^(logb(a+e))) for some constant e>0, and if a.f(n/b) < c.f(n) for some constant c<1 and all sufficiently large n, then T(n) = Θ(f(n))

    Now we need to compare f(n) with n^(logb(a)) .

    Note that the three cases do not cover all the possibilities for f(n). There is a gap between cases 1 and 2 when f(n) is smaller than n^(logb(a)) but not polynomially smaller. Similarly, there is a gap between cases 2 and 3 when f(n) is larger than n^(logb(a)) but not polynomially larger. If the function f(n) falls into one of these gaps, or if the regularity condition in case 3 fails to hold, you cannot use the master method to solve the recurrence.

    Now to solve the recurrence in question...

    a=3, b=2, f(n) = c = n^0

    so we have n^(log2(3)) ≈ n^(1.58) which is polynomially larger than n^0, falling under the 1st case. Then the time complexity is T(n) = Θ(n^(logb(a))) --> T(n) = Θ(n^1.58)