Algorithm CH4 Recurrences
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
Algorithm CH4 Recurrences
https://z-hwa.github.io/webHome/[object Object]/Algorithm/Algorithm-CH4-Recurrences/