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.

How about the recurrence --> $T(n) = 2 T(n/2) + 2^n$.

How can this be approached by master theorem?

share|improve this question
    
Have you tried case 3? (Wiki article), $2^n = \Omega(n^2)$? –  M.B. Jan 16 '13 at 14:50
    
Is $n$ going to take values other than a power of 2? –  Ron Gordon Jan 16 '13 at 15:02
    
we can assume that n can only take powers of 2.. i guess that would not impact this. correct me if i am wrong. –  csnoob Jan 16 '13 at 15:03
    
similar question –  Maesumi Jan 16 '13 at 15:48
    
AFAIK the master theorem does not solve the recurrence, it only gives asympotics. –  leonbloy Jan 16 '13 at 16:23
add comment

2 Answers

up vote 0 down vote accepted

Refer to my answer to your other question. Yes, indeed, the general version of the Master Theorem can be used here. The applicable case is if $T(n)=aT(n/b)+f(n)$ and if

  1. There is an $\epsilon>0$ for which $f(n)=\Omega(n^{\log_b a+\epsilon})$ and
  2. There is a $c<1$ such that $af(n/b)\le cf(n)$ for all $n$ sufficiently large, then

$$ T(n)=\Theta(f(n)) $$ In our case $a=b=2$ (so $\log_ab=1$) and $f(n)=2^n$. We see that

  1. $f(n)=2^n$ is bounded below by $n^{1+\epsilon}$. Taking $\epsilon=1$ we have $n^2\le 2^n$ for all $n\ge 4$, so $f(n)=\Omega(n^2)$
  2. $af(n/b)=2\cdot2^{n/2}=2^{1+n/2}$. Taking $c=1/2$ we have $2^{1+n/2}\le (1/2)2^n=2^{n-1}$ and this is satisfied for all $n\ge 4$.

We've satisfied both criteria for this case, so $$ T(n)=\Theta(2^n) $$ The intuition here is that the recursive part, $T(n)=2T(n/2)$ by itself is satisfied by $T(n)=n$ and this contribution to the result is totally swamped by the non-recursive part, $2^n$, so the answer is essentially just $\Theta(2^n)$.

Compare this with your other question: $T(n)=4T((2n)/3)+n^3\log n$. In this case, the recursive part is satisfied by $n^{\log_{3/2}4}\approx n^{3.419}$ and this part dominates the non-recursive part, $n^3\log n$, so the answer was $T(n)=\Theta(n^{\log_{3/2}4})$.

share|improve this answer
add comment

You can make the following substitution: $N=2^n$, $U(N) = T(\log_2{N})$:

$$U(N) - 2 U(N-1) = N$$

For the sake of simplicity, set $U(0) = 1$. (Not sure if you had this in mind.)

The solution to this equation is

$$U(N) = 3 \cdot 2^{N} - (N+2)$$

share|improve this answer
add comment

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.