Take quiz & check grades
Substitution method:
approach:
Guess a bound and use mathematical induction to prove the guess correct
note:
There is no recipe to find a correct guess.
What do we do?
 | Guess a possible solution |
| Use mathematical induction to find the constants and prove the solution works |
Example:
Take the running time
T(n) = 2*T(floor(n/2)) + n
| Let us try the solution T(n) = O(n * lg n) |
- with mathematical induction...
- a) must work in a boundary condition
- b) if valid for some n, see if expression holds true for another n
| b) see what happens with floor(n/2) T(n) <= c * floor (n/2) * lg(floor(n/2)) ... T(n) <= c* floor (n/2) * lg(floor(n/2)) + n T(n) <= c*n*lg(n/2)+n <=c*n*lg(n) - c*n*lg(2) + n <=c*n*lg(n) - c*n + n but for c>=1
|
| a) Now the boundary conditions: T(n)<=c*n*lg(n) ... for n>n0 T(2) = 4 T(3)=5 ..... T(2)<=c*2*lg(2) , T(3)<= c*3*lg(3) ... works for c>=2 for n0=2 |