Solving Recurrence using Master Theorem

Question

I do not see why this recurrence

T(n) = T(n/2)+ 2^n

of case 3 of Master Theorem fullfills the additional condition

a f(n/b) ≤ c f(n)

as 2^(n*(1/2)) ≤ c 2^n can not be fullfilled for 0 < c <1.

Answer 1

The requirement is that $af(n/b) \le k f(n)$ for some constant k < 1 and sufficiently large $n$. Suppose we take $k=1/2$, then it is true that $2^{n/2} \le k 2^n$ for $n \ge 2$, so the third case of the Master Theorem applies.