# Solve using Master's theorem

882 views

Solve this recurrence equation using Master's theorem

T(n) = 64 T(n/8) - n 2 log n

0

Master method cannot be applied, as F(N) = NLog N is decreasing .

1
$\tt T(n) = 64T(\frac{n}{8}) + n^2log(\frac{1}{n})$
Take on from here.
1
Still it falls between 1 and 2 .
1
yup master theorm not apllicable.
0
Akra Bazzi can be easily applied :)
0

Please tell how to apply Akra Bazii in the following recurrence :

T(n)=T(n/2)+ T(n/4) +n2

0
0

Following 2 case are possible :

1.) For worst case , recurrence relation is

T(n) = 2T(n/2) + n2   {as T(n/2) is larger problem then T(n/4) }

2.) For best case , recurrence relation is

T(n)= 2 T(n/4) + n2

As this  N2logN Function is decreasing Master Theorem can not be applied here..

0

what do u mean by (N2   LOG N ) IS DECREASING ?

the answer will be T(n)=theta(n^2 log^2 n)
master theorem can't be applied

T(n) = Θ($n^{2}$loglogn)

## Related questions

1
3.7k views
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
$T(a)=0 \hspace{0.2cm} if \hspace{0.2cm} a=1$ $T(a)=2T(a/2) + ak \hspace{0.2cm} if \hspace{0.2cm} a=2^{p}, p>0$ where $a=\frac{n}{k}$ Answer: $\Theta (n \log (\frac{n}{k}))$, This is while (n/k) is power of 2. How can I solve it using master theorem?