CSE 21
Math for Algorithms

Formulating Recurrences

(We focus on counting problems here.) To define a recurrence, you have to figure out how to illustrate a problem T(n) in terms of the same problem(s) for smaller inputs, e.g. T(n - 1), T(n - 2). There are a few ways to go about this.

1. Define T(n) = ... directly.

2. Work up from base cases.