title: complexity of the function T(N)=T(n/2)+2^n
body: <p>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 <code>2^n</code> in this question is causing me trouble. Here is what I have tried applying master theorem</p>
  
  <p><code>a=1</code>, <code>b=2</code> <code>n^log2(1)= n^0.65</code></p>
  
  <p>This leads to <code>n^0=1</code> I know that it has to be polynomial times that of <code>f(N)</code> which is <code>2^n</code> but I dont see how this is comparable with <code>2^n</code>.</p>
  
  <p>I tried with recursion tree as well but it got too complicated.</p>