Unit 1 · Foundational
The vocabulary for comparing solutions. Without asymptotic reasoning every later unit collapses into opinion about which approach feels faster.
Know
Big-O bounds growth from above, big-Omega from below, big-Theta when both match. Constants and lower-order terms are discarded because they do not change growth.
Apply
Reduce a cost expression to its dominant term and state which case it describes.
Watch out
Treating big-O as a synonym for worst case. They are independent ideas and questions exploit the confusion.
Know
A divide-and-conquer cost is written as a recurrence, and the shape of the recurrence determines the answer: halving with linear combining gives n log n, halving with constant work gives log n.
Apply
Match a recurrence against the standard shapes before attempting to expand it.
Watch out
Reporting the recurrence itself as the complexity rather than solving it.
Know
Recursion depth costs memory. A recursion over n elements holds n frames at once unless it is restructured.
Apply
State both time and space when analysing a recursive solution.
Watch out
Quoting only time for a deep recursion, missing a linear space cost that can matter more.
Know
Breaking a problem into independent subproblems is what makes divide and conquer, dynamic programming, and clean implementation all possible.
Apply
Identify the subproblems and whether they overlap before choosing a technique.
Watch out
Jumping to code before knowing whether subproblems repeat, which is the difference between divide and conquer and dynamic programming.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Given an algorithm that halves its input and does linear work per level, write and solve the recurrence, then state both time and space.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic