How do you solve this recurrence? I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.
Now the $4^{\textrm{th}}$ problem in that file is :
$$T(n) = 2^n T\left(\frac{n}{2}\right) + n^n.$$
The solution says it can't be solved using Master theorem, which is true. But I want to know how to solve it.
I tried thinking of some substitution but I'm not able to get anywhere since the recurrence contains terms $2^n$ and $n^n$ both. And if I expand the tree, it becomes really messy. Any solutions?
 A: Introducing $U(n)=T(n)/4^n$, one sees that $U(n/2)=T(n/2)/2^n$ hence the recursion over $(T(n))_n$ yields $U(n)=U(n/2)+(n/4)^n$.
Roughly speaking, this means that $U(n)=(n/4)^n+(n/8)^{n/2}+(n/16)^{n/4}+\ldots$ More rigorously, the $\ldots$ hides at most $\log_2n$ terms, each less than $(n/8)^{n/2}$, hence 
$$
(n/4)^n\leqslant U(n)\leqslant(n/4)^n+\log_2(n)\cdot(n/8)^{n/2},
$$
which implies
$$
n^n\leqslant T(n)\leqslant n^n+\log_2(n)\cdot(2n)^{n/2}.
$$
Since $\log_2(n)\cdot(2n)^{n/2}\ll n^n$, this yields $\lim\limits_{n\to\infty}T(n)/n^n=1$, hence $T(n)=\Theta(n^n)$.
A: Let $\begin{cases}k=\log_2n\\U(k)=T(n)\end{cases}$ ,
Then $U(k)=2^{2^k}U(k-1)+(2^k)^{2^k}$
$U(k)=2^{2^k}U(k-1)+2^{k\times2^k}$
$U(k+1)=2^{2^{k+1}}U(k)+2^{(k+1)2^{k+1}}$
$\therefore U_c(k+1)=2^{2^{k+1}}U_c(k)$
$U_c(k)=\Theta(k)\prod\limits_k2^{2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period
According to http://en.wikipedia.org/wiki/Indefinite_product#Rules ,
$U_c(k)=\Theta(k)2^{\sum\limits_k2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period
According to http://en.wikipedia.org/wiki/Indefinite_sum#Antidifferences_of_exponential_functions ,
$U_c(k)=\Theta(k)2^{2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period
Let $U(k)=2^{2^{k+1}}V(k)$ ,
Then $2^{2^{k+2}}V(k+1)=2^{2^{k+1}}2^{2^{k+1}}V(k)+2^{(k+1)2^{k+1}}$
$2^{2^{k+2}}V(k+1)=2^{2^{k+2}}V(k)+2^{(k+1)2^{k+1}}$
$V(k+1)=V(k)+2^{(k-1)2^{k+1}}$
$V(k)=\Theta(k)+\sum\limits_k2^{(k-1)2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period
$U(k)=\Theta(k)2^{2^{k+1}}+2^{2^{k+1}}\sum\limits_k2^{(k-1)2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period
$T(n)=\Theta(\log_2n)4^n+4^n\left(\sum\limits_k2^{(k-1)2^{k+1}}\right)_{k\to\log_2n}$ , where $\Theta(n)$ is an arbitrary periodic function with unit period
A: Hint: if  $k = T(n)/n^n$ then $$T(2n) = k 2^{2n}n^n +(2n)^{2n} = \left(k/n^n+1\right) (2n)^{2n}$$
