| name | algorithms |
| description | Algorithmic engineering theory, language-agnostic: complexity analysis (time/space, amortized), data-structure selection, algorithm families (divide & conquer, dynamic programming, greedy, graph, string), correctness reasoning with invariants, and space-time/approximation tradeoffs. Use when choosing a data structure, analyzing or reducing complexity, solving an algorithmic problem, reviewing code with non-trivial loops/recursion, or reasoning about scalability limits of an approach.
|
| allowed-tools | ["Read","Glob","Grep"] |
Algorithms & Complexity
IRON LAW: STATE THE COMPLEXITY (TIME AND SPACE, WITH n DEFINED) BEFORE
ACCEPTING ANY NON-TRIVIAL LOOP, RECURSION, OR DATA-STRUCTURE CHOICE.
Analysis Protocol
- Define n (and m, k…) precisely — "n = items rendered", not "the data".
- Derive time and space complexity; note amortized vs worst case where it
matters (dynamic arrays, hash maps).
- Check the realistic input size. O(n²) at n ≤ 100 is fine; at n = 10⁶ it is
an outage. Justify against actual scale, not asymptotics alone.
- Constant factors and memory locality matter at small n — an array beats a
linked structure in practice for most small collections.
Data-Structure Selection
| Need | Structure | Key costs |
|---|
| Index lookup, iteration | Dynamic array | O(1) index; O(n) middle insert; amortized O(1) append |
| Membership / key→value | Hash set/map | O(1) avg, O(n) worst; no order |
| Ordered keys, range queries | Balanced BST / B-tree | O(log n) ops, sorted iteration |
| FIFO/LIFO | Queue (ring buffer) / stack | O(1) ends |
| Priority ("next best") | Binary heap | O(log n) push/pop, O(1) peek |
| Prefix/string search | Trie | O(len) ops |
| Relationships/reachability | Graph (adjacency list) | BFS/DFS O(V+E) |
| Append-heavy text edits | Rope / gap buffer | avoids O(n) copies |
Selection question: which operations dominate, at what frequency, on how many
elements? Choose for the dominant operation.
Algorithm Families (recognition cues)
- Divide & conquer — independent subproblems (sorting, search): T(n) via
Master theorem.
- Dynamic programming — overlapping subproblems + optimal substructure
(edit distance, knapsack): memoize top-down or tabulate bottom-up; state
the recurrence first.
- Greedy — locally optimal is globally optimal ONLY with proof (exchange
argument); otherwise it's a heuristic — say so.
- Graph — model as nodes/edges first: BFS (shortest unweighted), Dijkstra
(non-negative weights), topological sort (dependencies), union-find
(connectivity).
- Two pointers / sliding window — sorted data or contiguous ranges in
O(n) instead of O(n²).
- Binary search — any monotonic predicate, not just sorted arrays.
Correctness
- State the loop invariant for non-obvious loops; check initialization,
maintenance, termination.
- Off-by-one audit at every boundary: empty input, single element, full
range, duplicates, overflow.
- Recursion: base case proven reachable; depth bounded (stack limits).
Tradeoff Levers
- Space ↔ time: caching/memoization, precomputed indices.
- Exact ↔ approximate: probabilistic structures (Bloom filter, HyperLogLog),
sampling — when error tolerance is explicit.
- Worst case ↔ typical case: randomization (quickselect), hashing.
- Optimal ↔ shippable: a clear O(n log n) beats a clever unproven O(n).
Related Skills
| Need | Skill |
|---|
| Proving it's actually faster | performance-engineering |
| Constant factors: cache locality, branch prediction | hardware-runtime |
| Property-based testing of invariants | testing |
| GPU-parallel formulations | metal, graphics |
