Time complexity

Question

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}$

Comments

Masters theorem can't be applied in all cases.

---

then how to solve...?

---

Try substitution method

Answer 1

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

Applying Master theorem n^log2¹ =n⁰=1

f(n)=2ⁿ 

Here 2ⁿ >1

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

T(n)=2^n.T(n/2)+nⁿ

Applying Master theorem n ^{log 2^n} =nⁿ

f(n)=nⁿ

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

Comments

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.

Answer 2

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.

Comments

i got ans for Q.3      2ⁿ logn  

for q. 4   n^n logn  

using recursion tree.

is it correct ?