Making Good Guesses

Start with the answer to something similar you've seen before.

Use common sense (?) to figure out which aspects of a formula aren't relevant.

For example, in T(n) = 2 T(n/2 + 17) + n, the 17 is probably not that important since n/2 + 17 is a lot like n/2 for large n.

The book lists a number of subtleties that crop up and heuristics to help get you out of trouble.


next up previous
Next: The Iteration Method Up: SOLVING RECURRENCES Previous: The Substitution Method