# Find the asymptotic growth of $t(n)$ satisfying $t(n)=2^nt(n/2)+n$

Find $\Theta$ of $t(n)$ for

$$t(n)=2^nt(n/2)+n .$$

I can't use Master Theorem because of $2^nt$ and althought I am familiar with other methods, I can't solve it. Is there a chance solve it using Recursive Tree method? If not, choose whatever method you can handle.

-
They don't matter for Landau classes, but what are the anchors? –  Raphael Dec 6 '11 at 19:06
There is no more notes or anchors in the task. –  Ondrej Janacek Dec 6 '11 at 19:21
Then $t$ is, technically, not well-defined; easy loop-hole. ;) –  Raphael Dec 6 '11 at 19:23
I haven't seen the word "anchor" in this context before, but I presume it means the same as the "base case" (e.g., $t(0)$ or $t(1)$ or some such). Am I correct? –  Srivatsan Dec 6 '11 at 19:42
@Srivatsan I think you are. –  Ondrej Janacek Dec 7 '11 at 8:53

Let $a=t(1)$. Then

\begin{align*} t(2^1)&=2^{2^1}a+2^1\;;\\ t(2^2)&=2^{2^2}\left(2^{2^1}a+2^1\right)+2^2\\ &=2^{2^2+2^1}a+2^{2^2+1}+2^2\;;\\ t(t^3)&=2^{2^3}\left(2^{2^2+2^1}a+2^{2^2+1}+2^2\right)+2^3\\ &=2^{2^3+2^2+2^1}a+2^{2^3+2^2+1}+2^{2^3+2}+2^3\;;\\ t(2^4)&=2^{2^4}\left(2^{2^3+2^2+2^1}a+2^{2^3+2^2+1}+2^{2^3+2}+2^3\right)+2^4\\ &=2^{2^4+2^3+2^2+2^1}a+2^{2^4+2^3+2^2+1}+2^{2^4+2^3+2}+2^{2^4+3}+2^4\;;\\ t(2^5)&=2^{2^5+2^4+2^4+2^3+2^2+2^1}a+2^{2^5+2^4+2^3+2^2+1}+2^{2^5+2^4+2^3+2}+2^{2^5+2^4+3}+2^{2^5+4}+2^5\;;\\ &\vdots\\ t(2^k)&=2^{2^{k+1}-2}a+\sum_{i=1}^k 2^{i+\sum_{j=i+1}^k 2^j}\\ &=2^{2^{k+1}-2}a+\sum_{i=1}^k 2^{i+2^{k+1}-2^{i+1}}\;, \end{align*}

so if $n=2^k$,

\begin{align*} t(n)&=2^{2n-2}a+\sum_{i=1}^k 2^{2n+i-2^{i+1}}\\ &=2^{2n-2}a+2^{2n}\sum_{i=1}^k 2^{i-2^{i+1}}\\ &=2^{2n-2}a+2^{2n}\frac{2^{k+1}-2}{4\sum_{i=0}^{k-1}2^{2^i}}\\ &=2^{2n-2}\left(a+\frac{2n-2}{\sum_{i=0}^{k-1}2^{2^i}}\right)\;. \end{align*}

Now $$2^{n/2}=2^{2^{k-1}}\le\sum_{i=0}^{k-1}2^{2^i}<2^{2^k}=2^n\;,$$ so

$$2^{2n-2}\left(a+\frac{2n-2}{2^n}\right)<t(n)\le2^{2n-2}\left(a+\frac{2n-2}{2^{n/2}}\right)\;,$$

or $$2^{2n-2}a+(2n-2)2^{n-2}<t(n)\le 2^{2n-2}a+(2n-2)2^{\frac{3n}2-2}\;.$$ Clearly the $2^{2n-2}a$ term is dominant, so $t(n)$ is $\Theta(2^{2n})$ for $n$ a power of $2$.

-
Typically, you will want to add an induction proof because of "...". –  Raphael Dec 6 '11 at 19:00
@Raphael: Of course, but I’m leaving that detail for the OP to fill in. –  Brian M. Scott Dec 6 '11 at 19:04
Ehm, and what is answer on the question? I need $\Theta$ not $\Omega$ –  Ondrej Janacek Dec 7 '11 at 10:12
@Andrew: $\Omega$ was a typo for $\Theta$, which I’ve now fixed. (That really should have been pretty clear if you looked at the last inequality.) –  Brian M. Scott Dec 7 '11 at 16:42

Introduce $s(n)=t(n)/4^n$ and $r(n)=n/4^n$, then $s(n)=s(n/2)+r(n)$. Introduce $\sigma(k)=s(2^k)$ and $\varrho(k)=r(2^k)$, then $\sigma(k)=\sigma(k-1)+\varrho(k)$, that is $$\sigma(k)=\sigma(0)+\sum\limits_{i=1}^k\varrho(i).$$ Since $\varrho(i)=2^i/4^{2^i}=2^{i-2\cdot2^i}$ is summable, $\sigma(0)\leqslant\sigma(k)\leqslant\sigma(0)+\tau$ for every $k$, where $\tau=\sum\limits_{i=1}^{+\infty}\varrho(i)$ is finite. In particular $t(2^k)/4^{2^k}=s(2^k)=\sigma(k)=\Theta(1)$, that is $t(2^k)=\Theta(4^{2^k})$.

-