in Algorithms
2,473 views
2 votes
2 votes

Solve this recurrence equation using Master's theorem

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

in Algorithms
by
2.5k views

4 Comments

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

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

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

0
0

4 Answers

0 votes
0 votes

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

1 comment

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

0
0
0 votes
0 votes
the answer will be T(n)=theta(n^2 log^2 n)
0 votes
0 votes
master theorem can't be applied
0 votes
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

2 votes
2 votes
2 answers
2