title: What is the recurrence relation and big O for T(n) = 2T(n-1) + O(N)?
body: <p>I thought it would be something like this...</p>
  
  <pre><code>T(n) = 2T(n-1) + O(n)
  
       = 2(2T(n-2)+(n-1)) + (n)
       = 2(2(2T(n-3)+(n-2))+(n-1))+(n)
       = 8T(n-3) + 4(n-2) + 2(n-1) + n
  </code></pre>
  
  <p>Which ends up being something like the summation of 2<sup>i</sup> * (n-i), and my book says this ends up being O(2<sup>n</sup>). Could anybody explain this to me? I don't understand why it's 2<sup>n</sup> and not just O(n) as the (n-i) will continue n times.</p>