# Solving recurrence $T(n) = 2 T(n/2) + 2^n$

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

How can this be approached by master theorem?

-
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

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

-

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

-