title: Solving recurrences: Substitution method
body: <p>I'm trying to follow Cormen's book "Introduction to Algorithms" (page 59, I believe) about substitution method for solving recurrences. I don't get the notation used for MERGE-SORT substitution: </p>
  
  <pre><code>T(n) ≤ 2(c ⌊n/2⌋lg(⌊n/2⌋)) + n
  ≤ cn lg(n/2) + n
  = cn lg n - cn lg 2 + n
  = cn lg n - cn + n
  ≤ cn lg n
  </code></pre>
  
  <p>Part I don't understand is how do you turn ⌊n/2⌋ to n/2 assuming that it denotes recursion. Can you explain the substitution method and its general thought process (especially the math induction part) in a simple and easily understandable way ? I know there's a great answer of that sort about big-O notation here in SO.</p>