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
    They don't matter for Landau classes, but what are the anchors?2011-12-06
  • 0
    There is no more notes or anchors in the task.2011-12-06
  • 0
    Then $t$ is, technically, not well-defined; easy loop-hole. ;)2011-12-06
  • 2
    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?2011-12-06
  • 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}

  • 0
    Typically, you will want to add an induction proof because of "...".2011-12-06
  • 0
    @Raphael: Of course, but I’m leaving that detail for the OP to fill in.2011-12-06
  • 0
    Ehm, and what is answer on the question? I need $\Theta$ not $\Omega$2011-12-07
  • 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})$.