Unit 1 · Foundational
The vocabulary for comparing solutions. Without asymptotic reasoning every later unit collapses into opinion about which approach feels faster.
What a strong answer looks like
A strong Unit 1 answer names the case, drops constants, and justifies the bound from the structure of the algorithm rather than from a measurement.
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.
Study move
Reduce four expressions to their tightest bound and name the case for each.
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.
Study move
Solve the merge sort and binary search recurrences and say which algorithm each describes.
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.
Study move
Compare space for recursive and iterative traversal of a list of length n.
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.
Study move
For two problems, say whether the subproblems overlap and what that implies.
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.
