Goals of the Lecture of September 1 2005

1. Given code, the students will be able to write a recurrence relation
for the time complexity of any simple recursive procedure.

2. The students will be able to solve any recurrence relation which
satisfies the input conditions of the Master Theorem, and will have an
understanding of why the Master Theorem holds.

3. The students will be able to solve many recurrence relations where
the left side is F(n) and the only function on the right side is F(n-1),
and will understand the relation between this problem and calculus.

4. The students will understand how substitution is used to solve some
recurrence relations which cannot fit into either of the above two
classes.