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

Question

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

How can this be approached by master theorem?

Answer 1

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

Answer 2

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