Def. Recurrence: an equation or an inequality that describes a function in terms of its value on smaller functions.

Recurrence Form

If. the problem size is small enough, (for a constant ), the solution takes constant time .
Else. divide problem into a sub-problems
- Each sub-problem is the size of the original
- It takes to solve one problem of size n/b
- It takes time to divide the problem into sub-problems
- It takes time to combine the solutions

Substitution Method

A general method and always works
Three main steps:
1. Guess the form of the solution:
  - You need a correct guess but it does not have to be accurate
2. Verify if recurrence is satisfied using induction
3. Solve for constants

Let . What is

Guess:
Assume:
Prove: by induction

(using )

(Desired - Residual)
(whenever )

This proved that however this bound is NOT tight!

Session 4 - Sub Method Example n2.png#invert

Session 4 - Substitution Example Tighter.png#invert

Recursion tree: models the costs (time) of a recursive execution of an algorithm
Always works, but we need to be careful when using …
Best used to generate good guesses for the substitution method.

Solve:

Session 4 - Recursion Tree Example.png#invert

The master method only applies to a particular family of recurrences of the form:

sub problems, each of size

Where:

(problem should get smaller)
for ( is asymptotically positive)

Session 4 - Master Method Tree.png#invert

Compare with (Number of leaves in recurrence tree)

Intuitively, the larger one of the two functions determines the solution to the recurrence.
Three common cases depending on asymptotic bounds of .
Case 1: for some
- grows polynomially slower than (by an factor)
- Solution:
Case 2:
- and grow at similar rates
- Solution:
Case 3: for some
- grows polynomially faster than (by an factor) and satisfies the regularity condition that for some constant and all suffieiently large n
- Solution: