Lecture 7: Divide and Conquer

Different Recall Function

Linear Function

such as:


Because ,

Square Function

such as:

Solving Recurrences

Substitution method

guess, then prove by induction ( So the guess is important! )

Lecture Example:

Right guess:

Recursion-tree method

Using a tree to represent the process.

Lecture Example:

First, calculate the height of the tree.

… Waiting for adding

Master Method

Form 1

对于递推式：

1. 如果存在常数，使得，那么
2. 如果，那么
3. 如果存在常数，使得，并且当对于常数c<1和所有足够大的N，那么

Form 2

对于递推式：

1. Waiting for adding

对于递推式：