490 views

Solve this recurrence equation using Master's theorem

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

| 490 views
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..

by Boss (18k points)
0

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

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

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

by Junior (677 points)