CSE 21

Math for Algorithms

(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.**

- Think about the "inductive case": what does the T(n) setting add to whatever you had before? Or: how do you get to T(n)? I often motivate my thinking by "building up" from the T(n - 1) scenario to the T(n) scenario, even if there's ultimately something else to do.
- Sometimes, there'll be multiple options (
*different blocks*) or cases (*"use" or "don't use" n*), which'll require multiple recursive calls. - If T(n) introduces elements to count which are independent of the ones that already exist (
*handshakes*), add those elements directly. - If T(n) introduces C elements for each of some set of elements that already exist (
*colored tiles*), add C * the relevant recursive call. **Just count all the elements that should be included in T(n)**, e.g.*all valid length-n strings*. Define a single term for each group of elements, making sure not to double-count, until you've exactly covered all the elements. Then sum up the terms. And you're done!

**2. Work up from base cases.**

- If you need somewhere to start, define base cases (presumably, you have to do this anyway). Write out the first X and try to figure out how the latest base case can be derived from the one(s) before it.