Unit 3, Day 10

Agenda

1. Warm-up: Spot the Bug — a nested loop that need not be nested
2. The rewrite clinic: three $O(n^2)$ fragments made $O(n)$ with a dictionary, on the board
3. Where it cannot be done, and how you would know

Things to do before our next class

• Journal: the trade you made — memory for time, or the reverse.