algorithmmaster-theorem

Understanding Master Theorem

Generic form: T(n) = aT(n/b) + f(n)

So i must compare n^logb(a) with f(n)

if n^logba > f(n) is case 1 and T(n)=Θ(n^logb(a))

if n^logba < f(n) is case 2 and T(n)=Θ((n^logb(a))(logb(a)))

Is that correct? Or I misunderstood something?

And what about case 3? When its apply?

Solution

  • I think you have misunderstood it. if n^logba > f(n) is case 1 and T(n)=Θ(n^logb(a))

    Here you should not be worried about f(n) as a result, what you are getting is T(n)=Θ(n^logb(a)). f(n) is part of T(n) ..and if you get the result T(n) then that value will be inclusive of f(n). so, There is no need to consider that part.

    Let me know if you are not clear.