Search code examples
algorithmtime-complexitymaster-theorem

Time complexity of a Divide and Conquer

I have Master theorem for finding complexities but the problem is Master theorem says

For a recurrence of form

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are following three cases: /******************logba means log of a with b as base **************/

  1. If f(n) = Θ(n^c) where c < Logba then T(n) = Θ(nLogba)

  2. If f(n) = Θ(n^c) where c = Logba then T(n) = Θ(ncLog n)

  3. If f(n) = Θ(n^c) where c > Logba then T(n) = Θ(f(n))

Now for My Problem 

T(n) = T(n/2) + n^2

My Solution c = 2 and logba = log of 2 with 1 as base = infinity So in which case it falls and what is the complexity

Solution

  • In your case b=2 and a=1 so Log_b(a) is log of 1 in base 2 and not log of 2 in base 1.

    See:

    T(n) = aT(n/b) + f(n)
T(n) =  T(n/2) + n^2

    As Log_b(a) = Log_2(1) = 0, you fall in case 3.