The first method is the Substitution Method.
The substitution method comprises 3 steps
1. Guess the form of the solution
2. Verify by Induction
3. Solve for constants.
We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence the name "Substitution Method".
This method is powerful, but we must be able to guess the form of the answer in order to apply it. If we are experienced in solving the recurrence problems then the substitution method can help, but if we are not then it will make no sense to apply it.
Example:
(1) T(n) = 4T(n/2) + n
Answer
Step 1: Guess the form of the solution
T(n) = 4T(n/2) + n ....(1)
My Thinking - if the variable form (n) is divided by 2 then most of the time log n comes in the result. Also, the running time, f(n) is n, so my sixth sense says that the result will not be lesser than (n log n), but in the compiling time, it is 4T(n/2). 4 is very greater than 2 so the result will be not lesser than O(n^2). I am sure that the answer will be in n^2 form but I will guess a bigger term and make it the big-Oh. So, my guess is O(n^3).
=> T(n) = O(n^3) (we guessed)
Step 2: Verify the induction
We need to prove that T(n) = c n^3
Assume, T(k) <= ck^3 (where k is any variable, and c is constant)
Equation (1) is T(n) = 4T(n/2) + n
=> T(k) <= 4c (n/2)^3 + n
=> <= c ((n^3)/2) + n
=> <= c n^3 - (c (n^3)/2 - n)
Here, (c (n^3)/2 - n) will be always positive if c is equal to or more than 2. So, what I assumed was true.
=> T(k) = O(k^3)
Step 3: Solve for constants
c n^3 - (c (n^3)/2 - n) => 0
if n => 1
and c => 2, then there is no negative term
Then, finally T(n) is O(n^3).
0 Comments