166: DSA - Complexity and Invariants
Learning outcomes
- estimate time and space complexity;
- distinguish input size from value magnitude;
- write and test an invariant before optimizing.
Practice
Compare nested loops, sorting, and a frequency map for duplicate detection. Explain best, average, and worst cases where they differ. Measure only after predicting complexity; benchmark inputs that expose the predicted growth.
Lesson
Let n be the number of values, not the largest value. A loop that scans 0..maxValue is O(maxValue), even if n is small. For hasDuplicate([4, 1, 4]), nested comparisons use O(1) extra space and O(n^2) time; sorting uses O(n log n) time and may mutate input; a set inserts each value once for expected O(n) time and O(n) space. Hash lookup is expected O(1), not a worst-case guarantee, so state that assumption.
Write the invariant before code: after processing the first i values, seen contains exactly the distinct values in that prefix. If the next value is already in seen, return true; otherwise insert it. The empty input and a single value return false. A correct optimization preserves the same result and contract, including whether input order and mutation matter.
Worked exercise
Implement firstRepeated(values), returning the first value whose second occurrence is encountered, or undefined. Walk [7, 3, 7, 3]: insert 7, insert 3, detect 7 and stop. Do not sort if “first” means encounter order. Decide how NaN, objects, and an actual undefined value are represented before implementation.
Tests and rubric
Test empty and one-item arrays, no repeat, adjacent and non-adjacent repeats, repeated values after the first repeat, negative numbers, NaN if supported, and a large input. Score 2 points each for correct contract, invariant, complexity (including auxiliary space), edge cases, and explaining the mutation/hash assumptions. Full credit requires tests that distinguish all three approaches.
Checkpoint
Solve “first repeated value” three ways and explain why a hash set changes space usage. State the loop invariant in one sentence.
Worked comparison
For values, a nested comparison is O(n^2) time and O(1) extra space. Sorting can reduce the scan to O(n log n), but mutates or copies and loses original positions unless they are carried along. A Set gives expected O(n) time and O(n) space. State the assumption behind hash-table complexity; it is not a proof of worst-case O(1).
Review questions
What is amortized complexity? Which input controls the bound? What evidence would make a slower algorithm preferable because it uses less memory or preserves order?