Substitution method for solving recurrences
First of all sorry for asking such a basic question.
But I am having difficulties understanding substitution method for solving recurrences.I am following Introduction to Algo.s -CLRS. As I am not able to find enough examples and ambiguity is the main concern.Especially the induction step.In the text books we have to prove f(n) implies f(n+1) but in CLRS this step is missing or may be I am not getting the example. Please explain step by step how to prove that O(n^2) is the solution for recurrence function T(n)=T(n-1)+n
Its the general steps of substitution method that I want to understand. If you could shed some light on strong mathematical induction and provide links to material on substitution method that'll be helpful also.
Answer
In substitution method, simply replace any occurance of T(k) by T(k-1) + k, and do it iteratively.
T(n) = T(n-1) + n =
= (T(n-2) + (n-1)) + n =
= T(n-3) + (n-2) + (n-1) + n =
= ... =
= 1 + 2 + ... + n-1 + n
From sum of arithmetic progression, you can get that T(n) is in O(n^2).
Note that substitution method is usually used to get an intuition on what the complexity is, to formally prove it - you will probably need a different tool - such as mathematical induction.
The formal proof will go something like that:
Claim: T(n) <= n^2
Base: T(1) = 1 <= 1^2
Hypothesis: the claim is true for each `k < n` for some `n`.
T(n) = T(n-1) + n <= (hypothesis) (n-1)^2 + n = n^2-2n + 1 < n^2 (for n > 1)