# 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?

-

## 3 Answers

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

-

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

$U_c(k)=\Theta(k)2^{\sum\limits_k2^{k+1}}$ , where $\Theta(k)$ is an arbitrary periodic function with unit period

$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

-

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

-
And?    –  Did Oct 2 '12 at 10:39
and $T(n) \in \Theta(n^n)$ as for large $n$ you have $k/n^n+1$ getting much closer to $1$ than $k$ –  Henry Oct 2 '12 at 10:48
This shows that T(2n)/(2n)^(2n) converges to 1 as soon as T(n)/n^(2n) converges to 0. Hence one needs to show that T(n)/n^(2n) does converge to 0. –  Did Oct 2 '12 at 10:55