Type the substitution guess and the key log identity for merge sort

Answer

T(n) <= c*n*lg(n) lg(n/2) = lg(n) - 1 => c*n*lg(n) - c*n + Theta(n) <= c*n*lg(n)

The identity lg(n/2) = lg n − 1 generates the −cn term that absorbs the Θ(n) driving cost. Without that absorbing term you would need the subtract-a-lower-order-term trick instead.