retagged by
519 views
0 votes
0 votes

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

retagged by

1 Answer

0 votes
0 votes

We can apply the extended Masters Theorem to this problem

Comparing the given equation with  T(n) = aT($\frac{n}{b}$) + nkLogp(n)

a= 2n, b=2, k=n, p=0 , we get a= bk  . Hence the solution to recurrence will be  

T(n)= Ɵ (nLogba.logp+1n) which is  nnLog n. 

edited by

Related questions

2 votes
2 votes
2 answers
3
3 votes
3 votes
4 answers
4
LavTheRawkstar asked Apr 16, 2017
4,378 views
T(n) = 100 T (n/99) + log(n!) Answer is T(n) = θ (n log n)a)answer is justifiedb)answer is not justifiedc)cannot be determinedd)none