Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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? –  Srivatsan Dec 6 '11 at 19:42
    
@Srivatsan I think you are. –  Ondrej Janacek Dec 7 '11 at 8:53

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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})$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.