title: Solving recurrence T(n) = 2T(n/2) + Θ(1) by substitution
body: <p>So I am pretty sure it is O(n) (but it might not be?), but how do you solve it with substitution?</p>
  
  <p>If you assume T(n) &lt;= c * n, what is the induction steps?</p>