in Algorithms edited by
1,214 views
3 votes
3 votes

How to apply Master's Theorem

(i) $T(n)= T(\frac{n}{2})+2^{n}$

(ii) $T(n)=2^{n}T(\frac{n}{2})+n^{n}$

in Algorithms edited by
by
1.2k views

3 Comments

Masters theorem can't be applied in all cases.
1
1
then how to solve...?
0
0
Try substitution method
0
0

2 Answers

1 vote
1 vote

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

Applying Master theorem nlog2=n0=1

f(n)=2n 

Here 2n >1

So, T(n)= O(2n)

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

Applying Master theorem n log 2^n =nn

f(n)=nn

So, T(n)=O(nn log n)

1 comment

Masters theorem is only applicable when Function is polynomial time greater than n^loga base b.So here masters theorem can not be applied.You may get wrong answer.
5
5
0 votes
0 votes
master theorem is applicable to following type only.

T(n)= a T($\frac{n}{b}$) + $n^k log^pn$

here both are not of form . so can't apply as a and b should be constant.  in the second case a is not constant it is a function of n. solve by reccurence relation. or by back substitution.

1 comment

edited by

i got ans for Q.3      2logn  

for q. 4   n^n logn  

using recursion tree.

is it correct ?

0
0