title: What is the time complexity of the recurrence T(n) = 2T(n-1) + 4
body: <p>What is the time complexity of the recurrence T(n) = 2T(n-1) + 4 ? </p>
  
  <p>I'm having serious problems with this. 
  I tried: </p>
  
  <p>T(n) = 2T(n-1)+4  = 2(2T(n-2)+4)+4 = 4T(n-2)+12= 4(2T(n-3)+4)+4 = 8T(n-3)+20 = 8(2T(n-4)+4)+4 =
   16T(n-4)+36 =…</p>
  
  <p>T(n) = 2^kT(n-k) + (4+2^(k+1))</p>
  
  <p>so it looks like T(n) = 2^n + (4+2^(n+1)) but it doesn't seem right... please help :(</p>