[next] [prev] [prev-tail] [tail] [up]

3.7.2 Substitution Method

Knowledge Base > Algorithm > Recurrence

Method 3.7.2.1.
In substitution method, first guess a bound and use mathematical induction to find the constants and show the solution is correct by Mathematical Induction (of method 3.7.1.1), or other techniques.

For instance, the recurrence function of Merge Sort (of equation 3.9.2),

(| Θ(1) if n = 1 |{ T(n) = | 2⋅T(⌊n⌋)+ n if n > 1 |( 2
We guess T(n) ≤ O(n ⋅ lg n) ⇒ T(n) ≤ c ⋅ n ⋅ lg n,∀c ≥ 0
Assume T(⌊n 2⌋) ≤ c ⋅⌊n 2⌋⋅ lg (⌊n 2⌋)
Prove T(n) ≤ c ⋅ n ⋅ lg n
Proof>
n- T (n) = 2 ⋅T(⌊2⌋)+ n ≤ 2 ⋅c⋅⌊n⌋ ⋅lg (⌊n-⌋)+ n 2 2 ≤ c ⋅n⋅lg(⌊n⌋)+ n (of equation 1.2.1) 2 ≤ c ⋅n⋅(lg n- 1)+ n (of equation 1.2.1) = c ⋅n⋅lgn + n- c⋅n = c ⋅n⋅lgn,c ≥ 1
This holds for c ≥ 2, because T(1) = 1 ≤ c ⋅ 1 ⋅ lg 1 = 0 does not hold.

[next] [prev] [prev-tail] [front] [up]