search
Log In
2 votes
882 views

Solve this recurrence equation using Master's theorem

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

in Algorithms 882 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
I think Answer is O(n^2).
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 

4 Answers

0 votes

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

0

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

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

Using Advanced master's theorem https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/
T(n) = Θ($n^{2}$loglogn)

Related questions

0 votes
5 answers
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.
asked Sep 28, 2018 in Algorithms mohitrai0_0 3.7k views
0 votes
1 answer
2
151 views
Solve given recurrence relation using Masters theorem: T(n) =T (n/2)+ n
asked Dec 4, 2016 in Algorithms sh!va 151 views
2 votes
2 answers
3
904 views
Solve using Masters theorem 2T (n/2) + n log n
asked Oct 29, 2016 in Algorithms sh!va 904 views
2 votes
1 answer
4
511 views
$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?
asked Apr 8, 2016 in Algorithms SomnathKayal 511 views
...