Solve $T(n) = 2^nT(n/2) + n^n$ Let $$T(n) = 2^nT(n/2) + n^n$$ Can't be solved using the master theorem, because the equation doesn't satisfy $$T(n) = aT(n/b) + f(n)$$
How would you approach this to find the time complexity?
 A: Divide by $2^{2n}$ and write $U(n)=T(n)/2^{2n}$:
$$T(n)/2^{2n}=T(n/2)/2^n+n^n/2^{2n}$$
$$U(n)=U(n/2)+(n/4)^n$$
Now the master theorem can be applied, giving $U(n)=\Theta((n/4)^n)$ and $T(n)=\Theta(2^{2n}(n/4)^n)=\Theta(n^n)$.
A: If
$T(n) = 
2^nT(n/2) + n^n
$,
then,
putting $2^m$ for $n$,
$T(2^m) 
= 2^{2^m}T(2^{m-1}) + (2^m)^{2^m}
= 2^{2^m}T(2^{m-1}) + 2^{m2^m}
$.
Let
$U(m) = T(2^m)$.
then
$U(m) 
= 2^{2^m}U(m-1) + 2^{m2^m}
$.
Since
$\sum 2^m = 2^{m+1}$,
divide by
$2^{2^{m+1}}$
to get
$\dfrac{U(m)}{2^{2^{m+1}}} 
= \dfrac{2^{2^m}U(m-1)}{2^{2^{m+1}}} + \dfrac{2^{m2^m}}{2^{2^{m+1}}}\\
= \dfrac{U(m-1)}{2^{2^{m+1}-2^m}} + 2^{m2^m-m-1}\\
= \dfrac{U(m-1)}{2^{2^m}} + 2^{m2^m-m-1}
$
Let
$V(m)
=\dfrac{U(m)}{2^{2^{m+1}}}
$.
This becomes
$V(m)
= V(m-1) + 2^{m2^m-m-1}
$
and this reduces to computing
$\sum 2^{m2^m-m-1}
$.
Another way is
$\begin{array}\\
T(n)  
&=2^nT(n/2) + n^n\\
&=2^n(2^{n/2}T(n/4) + (n/2)^{n/2}) + n^n\\
&=2^{n(3/2)}T(n/4) + 2^{3n/2}(n/2)^{n/2} + n^n\\
&=2^{n(3/2)}T(n/4) + (2^{3/2}n/2)^{n/2} + n^n\\
&=2^{n(3/2)}T(n/4) + (2^{1/2}n)^{n/2} + n^n\\
&=2^{n(3/2)}(2^{n/4}T(n/8) + (n/4)^{n/4}) + (2^{1/2}n)^{n/2} + n^n\\
&=2^{n(7/4)}T(n/8) + (n/4)^{n/4}) + (2^{1/2}n)^{n/2} + n^n\\
\end{array}
$
Not sure how to
nicely express this,
so I'll stop here.
