- Substitution method:
guess a bound.
use mathematical induction to prove that the guess is correct.
if the guess is wrong, refine the guess and try again. - Recursion-tree method:
convert the recurrence into a recursion tree.
use this tree to rewrite the function as a sum.
use techniques of bounding summations to solve the recurrence.
Substitution method
Step 1. Guess the form of the solution.
Step 2. Use mathematical induction to show that the guess is correct.
Attention:
- A good guess is vital when applying this method
- If the initial guess is wrong, the guess needs to be adjusted later.
解題步驟：先通過替換得出自己的猜想是否合理叫搁，然后找出特例范圍，測試特例寞酿，得出c的范圍督笆。再計算特例范圍外的的c的范圍简逮，對比得出答案。
實例
接上實例
The recursion tree method
The idea of the recursion tree method is to expand (iterate) the recurrence and express it as a summation of terms
題目
解
Important things to remember
- When using asymptotic notation, we take the fastest growing additive term and ignore its constant coefficient.
- Recall the difference between the defintions of O, W, Q and o, w: There exists some positive constant versus for any positive constant.
- Recall the hierarchy of growth rates.
To compare the order of growth of functions, use basic operations, take logarithms, or exponentiate. - In inductive proofs for statements like f (n) = O(g(n)), we have to use the same constant c throughout the proof.
