+1 vote
98 views
$\Large T(n) = 2^nT(\frac{n}{2}) + n^n$
0
Is $T(1)=1?$
0

yes

0
0
$T\left ( n \right )=2^{n}T\left ( \frac{n}{2} \right )+n^{n}$

$=2^{n}\left ( 2^{n/2}T\left ( \frac{n}{2^{2}} \right )+\left ( \frac{n}{2} \right ) ^{n/2}\right )+n^{n}$

$=2^{n+\frac{n}{2}+\frac{n}{4}+........}T\left ( 1 \right )+n^{n}+\left ( \frac{n}{2} \right )^{n/2}+\left ( \frac{n}{4} \right )^{n/4}+.......1$

$=2^{n}+n^{n}+............$

$=O(n^{n})$
0

@srestha why can't we use master theorem here.using that ans comes out $n^{n}logn$

0
no, we cannot apply master theorem because f(n) is not polynomial function here

It is an exponential func.
0
We cant apply master theorem because a is not constant here

+1 vote
1
+1 vote
2