Cheat Sheet: Structures, Algorithms, and Costs

This is the summary page to revisit before an interview. Everything here appeared somewhere in the course; the value of having it in one place is that you can check your recall in a few minutes instead of rereading sixteen chapters.

Complexities follow the convention set out in "How We State Complexity in This Course": time is worst case unless labelled average, space means extra space beyond the output, and the recursion stack always counts.

The structures