1
$\begingroup$

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.

  • 0
    @Srivatsan I think you are.2011-12-07

2 Answers 2

3

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(2^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)

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

  • 0
    @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.)2011-12-07
1

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