Algorithm CH4 Recurrences

A recurrence is a function is defined in terms of

• one or more base cases, and
• itself, with smaller arguments

Ex.

Substitution method

• T(n) is always constant for any constant n.
• Since we are ultimately interested in asymptotic solution to a recurrence, it will always be possible to choose base cases that work
• When we want an asymptotic solution to a recurrence, we don’t worry about the base cases in our proofs.
• When we want an exact solution, then we have to deal with base cases.

For the substitution method:

• Name the constant in the additive term
• Show the upper (O) and lower (Ω) bounds separately. Might need to use different constants for each notation

substract off a lower-order term may help

waring

需要做回假設時使用的準確長相

Recurrence trees

Goal of the recursion-tree method

• a good guess for the substitution method
• a direct proof of a solution to a recurrence (provided by carefully drawing a recursion tree)

diff. depth

master method

for regularity condition