Solve $T(n) = 2^nT(n/2) + n^n$

Question

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?

Answer 1

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)$.

Answer 2

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.