Question

Let T(n) = 3T(n/2)+f(n) and f(n) = Θ(n), use the master method to solve T(n)

Answer 1

Master method:
---------------
T(n) = aT(n/b) + f(n)
If f(n) = Θ(n^c) where c < Logb(a) then T(n) = Θ(n^Logb(a))
If f(n) = Θ(n^c) where c = Logb(a) then T(n) = Θ((n^c)(Log(n)))
If f(n) = Θ(n^c) where c > Logb(a) then T(n) = Θ(f(n))


T(n) = 3T(n/2)+f(n)
and given f(n) = Θ(n)

Then T(n) = 3T(n/2)+Θ(n)
Where a = 3, b = 2, f(n) = Θ(n) and then c is 1

Logb(a)
= Log2(3)
= 1.584962500721156

c < Logb(a) is True.
So, It applies the rule T(n) = Θ(n^Logb(a))

T(n) = Θ(n^Log2(3))