Is it valid recurrence for Master Theorem? $T(n)=T(n/2)+2^n$

Question

So in class we did the following

$T(n)=T(n/2)+2^n$ -----> Case 3 $ O(2^n)$

When I read in the internet it says that I cannot apply Master Theorem if f(n) is not polynomial. So what is the true case? Is it $O(2^n)$ or $T(n)=T(n/2)+2^n$ is not applicable for Master Theorem?

Thanks

Answer 1

I'm sorry for my wrong, I revision and edit my previous comment:

As I know at all in this type of problems we can not use Master Theorem. But here by chance and because amount of 2^n is too much we see the true answer is same with Master Theorem method but this isn't reason for the truth of useing Master Theorem in this type of problems.

In summary, Master Theorem only use when the difference between two functions is the power of the 'n' and ( n>0 ) , or the power of (log n). And of course, when the two functions are equal.

And I think the answer of T(n)=T(n/2)+2n is : T(n) ∈ θ(2^n)