Introduction
Syllabus
Guidelines for labs
Lab sections
Take quiz & check grades
| |
Recurrences
Purpose of this chapter:
to let you compute the bounds on the running time of a given algorithm when
the expression for T(n) is not readily available as a function of n. T(n) is available as
a recurrence.
3 methods: (pages 53 to 64)
|
| guess a bound and use mathematical induction to prove the guess correct |
|
| iteration method
| converts the recurrence into a summation and try to find the solution |
|
|
| can only be used for recurrences of the form T(n)=aT(n/b) + f(n). It does not cover all
the cases. |
|
Recurrences:
The running time is expresssed by a recurrence relation:
Example:
T(n) is:
| Teta(1) if n=1 |
| 2* T(n/2)+Teta(n) if n>1 |
|