Question

Solve using the Master Method

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

Answer 1

Solution:

Masters Theorem:

if the function is of the form

T(n) = at(n/6) + f(n)

,a >=1,6 > 1

then

if
f(n) = O(n) and c < logga then T(n) = O(nlogia)
---------------(eq 1)

if
f(n) = O(n) and c=logya then Tn) = O(n"logn))
------------(eq 2)

if
f(n) = O(n) and c> logga then T(n) = O(fn))
--------------------(eq 3)

So,let the given equation be,

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

in the above equation we can identify the values of

$a=3$

$b=2$

f(n) = n

$c=1$`

Now,

log23 = 1.58
and $c=1$

therefore we can conclude that,

c<log23

therefore from eq 1 of masters theorem we have,

$T(n)=O(n^{log_{b}a})$

$T(n)=O(n^{log_{2}3})$

$T(n)=O(n^{1.58})$