complexity of the function T(N)=T(n/2)+2^n

Question

I am a student taking the algorithm course at university. I know how to apply a few recursive techniques to find the running cost of simpler functions but the 2^n in this question is causing me trouble. Here is what I have tried applying master theorem

a=1, b=2 n^log2(1)= n^0.65

This leads to n^0=1 I know that it has to be polynomial times that of f(N) which is 2^n but I dont see how this is comparable with 2^n.

I tried with recursion tree as well but it got too complicated.

Answer 1

You can apply the third case of the master theorem described here because f(n) is equal to Ω(nloga).

Here, 
f(n) = 2^n , and
Ω(n^log 1) = Ω(1)

2^n = Ω(1) , because for some constant c>0 and all large enough n, 2^n ≥ c*1.

So T(n) = f(n)
T(n) = O(2^n)