CSE 21
Math for Algorithms & Systems Analysis

Formulating Recurrences

(Note: 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.

back