Search code examples
algorithmmathcomputer-sciencerecurrenceinduction

Substitution Method : Why this recurrence changes inequality & equality sign And Why inductive step used smaller values as a next value

I was reading CLRS book to understand solving recurrences using Substitution method and found following example:

   Recurrence, T(n) = 2T(n/2) + n
   Guess Solution, T(n) = O(nlgn)
   Proof that T(n) ≤ cnlgn

enter image description here

My questions are:

Q1: why the solving equation changes their signs between inequality & equality sign ≤ , = ?

Q2: We know that in mathematical induction, inductive step is the next value,So if current value is n then next value should be (n+1).But Why they used n/2 as the next inductive step ?

Please help me to explain these question.It will rally help me to understand Substitution Method.Thanks

Solution

  • Q1 : The two equalities are just rewritings of the previous line since log(a/b) = log(a) - log(b) and log(2) = 1

    Q2 : For the induction step, since we write T(n) in function of T(n/2), one step is directly a 2-factor. If the recurrence formula was T(n) = f(T(n-1)), you would have the classical induction step with a 1-addition.

    Note also that you assume in this proof that T(1) can be done in constant time.