Algorithms and data structures¶
Data structures organize state; algorithms transform or query it. The engineering task is to match operations and constraints to a structure, prove the behavior that matters, and measure the whole workload.
Use Module 3: Data structures and algorithms for guided implementation and benchmarking.
Start with operations¶
Before selecting a structure, write down:
- what must be inserted, removed, found, or traversed;
- whether ordering, uniqueness, priority, or range queries matter;
- expected and maximum size;
- ratio of reads to writes;
- required worst-case behavior;
- memory, persistence, and concurrency constraints.
“Fast lookup” is incomplete. Lookup by index, exact key, prefix, range, minimum priority, or graph reachability requires different structure.
Complexity¶
Asymptotic notation describes growth as input size increases:
- \(O(f(n))\): asymptotic upper bound;
- \(\Omega(f(n))\): asymptotic lower bound;
- \(\Theta(f(n))\): matching upper and lower bound.
State what \(n\) represents and which case is being described. An average-case claim also needs an input or probability assumption.
Complexity tables usually use a unit-cost model for primitive operations. Real costs can depend on value size: hashing or comparing a string, copying an object, and arithmetic on an arbitrary-precision integer are not inherently \(O(1)\).
Common growth classes:
| Class | Typical example |
|---|---|
| \(O(1)\) | array index access |
| \(O(\log n)\) | binary search in sorted random-access data |
| \(O(n)\) | scan every item |
| \(O(n\log n)\) | general comparison sorting |
| \(O(n^2)\) | compare every pair |
| \(O(2^n)\) | enumerate subsets |
| \(O(n!)\) | enumerate permutations |
Asymptotic analysis omits constants and lower-order terms. It predicts scaling, not wall-clock time.
Amortized complexity¶
An operation may occasionally be expensive while a sequence remains cheap. A dynamic array append is commonly \(O(1)\) amortized because occasional resizing work is spread across many appends. Amortized is not the same as average-case probability.
Space complexity¶
Distinguish total storage from auxiliary space added by the algorithm. Include recursion depth, temporary copies, indexes, queues, and retained caches.
Core structures¶
| Structure | Strength | Important cost or condition |
|---|---|---|
| Dynamic array | indexed access and compact traversal | middle insertion or deletion shifts elements |
| Linked list | insertion at a known node | finding a node and random access are linear; poor locality is common |
| Stack | last-in, first-out access | only the top is directly available |
| Queue/deque | first-in, first-out or both ends | choose an implementation with constant-time end operations |
| Hash map | exact-key lookup, average \(O(1)\) | \(O(n)\) space, collision/worst-case behavior, no sorted-key guarantee |
| Hash set | membership and uniqueness | same hashing assumptions as a map |
| Heap | inspect/remove highest or lowest priority | arbitrary search remains linear |
| Balanced search tree | ordered keys and range traversal | operations are typically \(O(\log n)\) with more pointer overhead |
| B-tree family | ordered data optimized for block storage | implementation and tuning usually belong to a database/filesystem |
| Trie | prefix queries over sequences | memory can be high; cost depends on key length |
| Graph adjacency list | sparse relationships and neighbor traversal | lookup depends on neighbor representation |
| Graph adjacency matrix | dense graph and constant-time edge test | \(O(V^2)\) space |
Language containers may make stronger guarantees than the abstract structure. For example, some hash-map implementations preserve insertion order, but that does not make keys sorted.
Selection examples¶
| Requirement | Reasonable starting point |
|---|---|
| Preserve a small sequence and scan it | dynamic array/list |
| Repeated exact lookup by unique ID | map keyed by ID |
| Maintain uniqueness only | set |
| Process work in arrival order | queue/deque |
| Always take the next highest-priority item | heap |
| Query ordered ranges while mutating | balanced tree or database index |
| Traverse dependencies or relationships | adjacency list |
Start with the simplest structure meeting the current operation. A second index accelerates reads but consumes memory and must remain consistent after every mutation.
Invariants¶
An invariant is a property that must remain true:
- map keys are unique;
- heap parent priority dominates child priority;
- binary-search input is sorted under the same comparator;
- a queue removes in insertion order;
- a graph traversal does not repeatedly process visited vertices.
State invariants before implementation. Tests should exercise empty input, minimal input, boundaries, duplicates, absent targets, invalid state, and large enough input to expose scaling mistakes.
Correctness reasoning¶
A useful algorithm argument has three parts:
- Precondition: what must be true before execution.
- Invariant: what remains true after each step.
- Postcondition and termination: why the algorithm stops with the required result.
For recursive algorithms, define a smaller subproblem and a base case. For iterative algorithms, define the meaning of processed and unprocessed regions.
Tests find counterexamples; they do not prove correctness for every input. Pair examples with reasoning when the algorithm is important.
Searching¶
| Method | Precondition | Time | Useful when |
|---|---|---|---|
| Linear search | none | \(O(n)\) | data is small, unsorted, or searched once |
| Binary search | sorted random-access data | \(O(\log n)\) | sort cost is already paid or many searches reuse order |
| Hash lookup | hashable key and maintained index | \(O(1)\) average, \(O(n)\) worst | repeated exact-key lookup |
| Tree lookup | maintained ordered tree | \(O(\log n)\) when balanced | lookup and ordered/range operations coexist |
Do not quote lookup complexity without index construction and maintenance cost. See Searching algorithms.
Sorting¶
Sorting choices depend on:
- comparison versus bounded-key assumptions;
- worst-case and expected time;
- auxiliary memory;
- whether equal-key input order must be preserved (stability);
- whether data is nearly sorted;
- whether data fits in memory.
Production code should normally use the language or database sort. Implement a sort to learn its invariant, not to replace a maintained implementation.
Comparison sorting has a lower bound of \(\Omega(n\log n)\) in the general comparison decision-tree model. Algorithms exploiting key structure can have different bounds under different assumptions.
See Sorting algorithms.
Graphs¶
A graph has vertices and edges. Before choosing an algorithm, state:
- directed or undirected;
- weighted or unweighted;
- possible negative weights;
- sparse or dense;
- whether parallel edges or self-loops are allowed.
With an adjacency list:
- breadth-first search finds shortest paths by edge count in an unweighted graph;
- depth-first search supports reachability, cycle reasoning, and traversal order;
- both visit reachable vertices and edges in \(O(V+E)\) time when neighbor operations are constant-time.
BFS is not a weighted shortest-path algorithm. Dijkstra requires non-negative edge weights. Negative weights require another method and negative cycles may make a finite shortest path undefined.
See Graph algorithms.
Design paradigms¶
- Divide and conquer: split into independent subproblems, solve, combine.
- Dynamic programming: reuse overlapping subproblems with a state and recurrence.
- Greedy: make a locally best choice supported by an exchange or structural proof.
- Backtracking: explore choices and abandon a partial candidate when it cannot succeed.
- Branch and bound: prune using a bound on the best possible completion.
These labels do not establish correctness. The recurrence, invariant, exchange argument, or bound does.
Continue with Dynamic programming, Greedy algorithms, and Other paradigms only when the problem calls for them.
Recursion and iteration¶
Recursion can express trees and divide-and-conquer clearly, but each active call consumes stack space unless the language guarantees an optimization. Deep or adversarial input can overflow the call stack.
An explicit stack makes memory ownership and traversal order visible. Choose between recursion and iteration for clarity, depth bounds, cancellation, and runtime behavior—not because one is universally faster.
Benchmarking decisions¶
Use complexity to form a hypothesis, then measure equivalent behavior:
- generate representative and adversarial inputs;
- verify every implementation returns the same result;
- separate setup from the operation being compared;
- test increasing input sizes;
- repeat runs and retain the distribution;
- measure end-to-end impact and memory as well as the inner operation;
- record environment and commands.
A faster lookup may not matter when parsing, network I/O, or saving all records dominates the request.
Common mistakes¶
- Choosing a structure by popularity instead of access pattern.
- Treating average-case hash lookup as a worst-case guarantee.
- Applying binary search to data that is not sorted by the same comparator.
- Using a heap when arbitrary lookup is also required.
- Reporting Big O as measured elapsed time.
- Optimizing one operation while ignoring index construction and mutation.
- Forgetting that representations change graph complexity.
- Adding a custom algorithm where the standard library is clearer and better tested.