title: Recursion and Big O
body: <p>I've been working through a recent Computer Science homework involving recursion and big-O notation. I believe I understand this pretty well (certainly not perfectly, though!) But there is one question in particular that is giving me the most problems. The odd thing is that by looking it, it looks to be the most simple one on the homework.</p>
  
  <p>Provide the best rate of growth using the big-Oh notation for the solution to the following recurrence?</p>
  
  <p>T(1) = 2</p>
  
  <p>T(n) = 2T(n - 1) + 1 for n>1 </p>
  
  <p>And the choices are:</p>
  
  <ul>
  <li>O(n log n)</li>
  <li>O(n^2)</li>
  <li>O(2^n)</li>
  <li>O(n^n)</li>
  </ul>
  
  <p>I understand that big O works as an upper bound, to describe the most amount of calculations, or the highest running time, that program or process will take. I feel like this particular recursion should be O(n), since, at most, the recursion only occurs once for each value of n. Since n isn't available, it's either better than that, O(nlogn), or worse, being the other three options.</p>
  
  <p>So, my question is: Why isn't this O(n)?</p>