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?
 A: 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 


*

*There is an $\epsilon>0$ for which $f(n)=\Omega(n^{\log_b a+\epsilon})$ and

*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


*

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

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