Algorithms & Data Structures

An algorithm is a finite, unambiguous sequence of well-defined instructions for solving a class of problems. A data structure is an organization of data that enables efficient access and modification. Together they form the mechanical foundation of all computation. This skill catalogs the canonical algorithms and data structures with complexity analysis, implementation notes, and selection heuristics.

Agent affinity: knuth (algorithm analysis, literate implementation), turing (computability, theoretical limits)

Concept IDs: code-sorting-algorithms, code-searching-algorithms, code-big-o-notation, code-dynamic-programming

Complexity Analysis at a Glance

Before studying individual algorithms, internalize the complexity hierarchy. Every algorithm has a time cost and a space cost, each expressed as a function of input size n.

Class	Name	Example
O(1)	Constant	Array index access, hash table lookup (average)
O(log n)	Logarithmic	Binary search, balanced BST lookup
O(n)	Linear	Linear search, single traversal
O(n log n)	Linearithmic	Merge sort, heap sort, efficient comparison sorts
O(n^2)	Quadratic	Bubble sort, insertion sort (worst), naive string matching
O(n^3)	Cubic	Naive matrix multiplication, Floyd-Warshall
O(2^n)	Exponential	Brute-force subset enumeration, naive recursive Fibonacci
O(n!)	Factorial	Brute-force permutation, naive TSP

Big-O gives the asymptotic upper bound. Big-Omega gives the lower bound. Big-Theta gives the tight bound (both upper and lower). When we say "merge sort is O(n log n)," we mean its worst-case running time grows no faster than c * n * log(n) for some constant c and sufficiently large n. More precisely, merge sort is Theta(n log n) because its best, average, and worst cases all share this growth rate.

Amortized analysis applies when individual operations vary in cost but the average over a sequence is predictable. The classic example is dynamic array resizing: a single push may cost O(n) when the array doubles, but amortized over n pushes, each costs O(1).

Part 1 -- Sorting Algorithms

Sorting is the most studied problem in computer science. Comparison-based sorting has a proven lower bound of Omega(n log n) -- no comparison sort can do better in the worst case. Non-comparison sorts (radix, counting, bucket) can beat this bound when the data admits it.

1.1 -- Bubble Sort

Mechanism: Repeatedly walk the array, swapping adjacent elements that are out of order. After pass k, the k-th largest element is in its final position.

Complexity: O(n^2) time worst/average, O(n) best (already sorted, with early-exit optimization). O(1) space. Stable.

When to use: Almost never in production. Its value is pedagogical -- it is the simplest sorting algorithm to understand and proves that sorting is achievable through local comparisons alone.

The early-exit optimization. If a full pass completes with zero swaps, the array is sorted. This gives O(n) best case, making bubble sort adaptive -- it benefits from pre-existing order.

1.2 -- Insertion Sort

Mechanism: Build the sorted portion one element at a time. For each new element, shift larger elements right and insert into the correct position.

Complexity: O(n^2) worst/average, O(n) best (nearly sorted). O(1) space. Stable. Adaptive.

When to use: Small arrays (n < 20-50), nearly sorted data, online sorting (elements arrive one at a time). Many optimized sort implementations (including Timsort) use insertion sort for small partitions.

Why it beats bubble sort. Insertion sort performs at most n-1 comparisons on sorted input and does fewer swaps on average because it moves elements directly to their correct position rather than bubbling them one step at a time.

1.3 -- Selection Sort

Mechanism: Find the minimum element in the unsorted portion and swap it to the front. Repeat.

Complexity: O(n^2) in all cases. O(1) space. Not stable (swaps can break equal-element ordering). Not adaptive.

When to use: When write operations are expensive (flash memory, EEPROM) -- selection sort performs exactly n-1 swaps regardless of input. This is its only practical advantage.

1.4 -- Merge Sort

Mechanism: Divide the array in half, recursively sort each half, merge the sorted halves.

Complexity: Theta(n log n) in all cases. O(n) auxiliary space (for the merge buffer). Stable.

The merge operation. Two pointers walk the two sorted halves. At each step, the smaller element is copied to the output. This is O(n) per level, and there are log(n) levels, giving n log n total.

When to use: When stability is required, when worst-case guarantees matter, when data is on disk (merge sort's sequential access pattern is cache-friendly for external sorting). Java's Arrays.sort for objects uses a merge sort variant (Timsort).

Recurrence relation: T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2), T(n) = Theta(n log n).

1.5 -- Quick Sort

Mechanism: Choose a pivot, partition the array so all elements less than the pivot come before it and all greater come after, recursively sort the partitions.

Complexity: O(n log n) average, O(n^2) worst (pathological pivot choices). O(log n) space (recursion stack, in-place). Not stable (Lomuto/Hoare partition swaps non-adjacent elements).

Pivot selection strategies. Random pivot gives O(n log n) expected time. Median-of-three (first, middle, last) avoids worst case on sorted input. Introselect (switch to heap sort after recursion depth exceeds 2 log n) guarantees O(n log n) worst case -- this is introsort, used by C++ std::sort.

When to use: Default choice for in-memory sorting when stability is not required. Cache performance is excellent (sequential access within partitions). In practice, quicksort with good pivot selection beats merge sort due to lower constant factors.

Why O(n^2) worst case is rare. With random pivot selection, the probability of O(n^2) behavior is vanishingly small. The expected number of comparisons is 2n ln n, approximately 1.39 n log2 n.

1.6 -- Heap Sort

Mechanism: Build a max-heap from the array (O(n) via Floyd's algorithm), then repeatedly extract the maximum and place it at the end.

Complexity: Theta(n log n) in all cases. O(1) space. Not stable.

When to use: When guaranteed O(n log n) is needed without the O(n) auxiliary space of merge sort. The constant factor is larger than quicksort's, making it slower in practice for in-memory sorting. Used as the fallback in introsort.

1.7 -- Radix Sort (Non-Comparison)

Mechanism: Sort by each digit position, from least significant to most significant, using a stable sub-sort (counting sort) at each position.

Complexity: O(d * (n + k)) where d is the number of digits and k is the base. For fixed-width integers, this is O(n). Space: O(n + k).

When to use: When sorting integers or fixed-length strings where the number of digits d is small relative to log n. Radix sort is not comparison-based and therefore not subject to the Omega(n log n) lower bound.

Sorting Selection Heuristic

Situation	Algorithm	Reason
Small array (n < 50)	Insertion sort	Low overhead, adaptive
General purpose, stability needed	Merge sort / Timsort	Guaranteed O(n log n), stable
General purpose, in-place	Quicksort (introsort)	Best average-case cache behavior
Guaranteed worst-case, in-place	Heap sort	No auxiliary space, no pathological cases
Integers, fixed-width keys	Radix sort	O(n) when d is bounded
Nearly sorted	Insertion sort / Timsort	Adaptive algorithms exploit existing order
Minimizing writes	Selection sort	Exactly n-1 swaps

Part 2 -- Searching Algorithms

2.1 -- Linear Search

Mechanism: Walk the collection from start to end, checking each element.

Complexity: O(n) worst/average, O(1) best. Works on unsorted data.

When to use: Unsorted data, small collections, when the cost of sorting exceeds the cost of repeated linear searches (breakeven around log n searches).

2.2 -- Binary Search

Mechanism: Maintain low and high indices. Compare the target with the middle element. If less, search the left half; if greater, search the right half. Repeat.

Complexity: O(log n) worst/average. Requires sorted data.

The off-by-one trap. Binary search is notoriously error-prone to implement. The loop invariant must be stated explicitly: "the target, if present, lies in [low, high]." Use half-open intervals [low, high) to avoid confusion. Test on arrays of size 0, 1, 2, and 3.

Variants. Lower bound (first element >= target), upper bound (first element > target), and exact match. The C++ STL provides std::lower_bound and std::upper_bound. Python's bisect module provides bisect_left and bisect_right.

2.3 -- Graph Search: BFS and DFS

BFS (Breadth-First Search). Explore all neighbors at depth d before depth d+1. Uses a queue. Finds shortest paths in unweighted graphs. O(V + E) time, O(V) space.

DFS (Depth-First Search). Explore as deep as possible before backtracking. Uses a stack (explicit or call stack). Detects cycles, finds connected components, performs topological sort. O(V + E) time, O(V) space.

When to use BFS vs DFS. BFS for shortest path in unweighted graphs, level-order traversal. DFS for cycle detection, topological sort, strongly connected components, maze solving.

2.4 -- Dijkstra's Algorithm

Mechanism: Greedy single-source shortest path. Maintain a priority queue of (distance, vertex) pairs. Extract the minimum, relax all its edges.

Complexity: O((V + E) log V) with a binary heap. O(V^2) with a simple array (better for dense graphs).

Constraint: No negative edge weights. For graphs with negative edges, use Bellman-Ford (O(VE)).

2.5 -- A* Search

Mechanism: Like Dijkstra but guided by a heuristic h(n) estimating the cost from n to the goal. Expands the node with the lowest f(n) = g(n) + h(n).

Complexity: Depends on the heuristic. With an admissible (never-overestimates) and consistent heuristic, A* is optimal and complete.

When to use: Pathfinding in games, robotics, navigation -- any domain where a good heuristic is available.

Part 3 -- Fundamental Data Structures

3.1 -- Arrays

Contiguous memory block with O(1) random access by index. O(n) insertion/deletion in the middle (shift required). Dynamic arrays (ArrayList, Vec, list) amortize append to O(1) via doubling.

3.2 -- Linked Lists

Nodes connected by pointers. O(1) insertion/deletion at known position. O(n) access by index. Singly linked (forward only), doubly linked (forward and backward), circular.

When to prefer over arrays. Frequent insertions/deletions at arbitrary positions with known references. In practice, arrays win due to cache locality -- linked lists have poor spatial locality.

3.3 -- Stacks and Queues

Stack: LIFO (Last In, First Out). Push and pop are O(1). Used for function call tracking, expression evaluation, undo systems, DFS.

Queue: FIFO (First In, First Out). Enqueue and dequeue are O(1). Used for BFS, task scheduling, buffering.

Deque: Double-ended queue. O(1) insert/remove at both ends. Used for sliding window problems.

3.4 -- Hash Tables

Mechanism: Map keys to array indices via a hash function. O(1) average lookup, insert, delete. O(n) worst case (all keys hash to the same bucket).

Collision resolution. Chaining (linked list per bucket) or open addressing (linear probing, quadratic probing, double hashing). Load factor management: resize when load factor exceeds threshold (typically 0.75).

When to use. Fast key-value lookup, membership testing (hash sets), counting (frequency maps). The single most important data structure in practical programming.

3.5 -- Trees

Binary Search Tree (BST). Left child < parent < right child. O(log n) average operations, O(n) worst (degenerate/linear tree).

Balanced BSTs. AVL trees (strict balance, O(log n) guaranteed), Red-Black trees (relaxed balance, O(log n) guaranteed, fewer rotations). Used in standard library ordered maps (C++ std::map, Java TreeMap).

B-Trees. Multi-way balanced trees optimized for disk access. Each node holds multiple keys and has multiple children. Used in databases and file systems.

3.6 -- Heaps

Binary Heap. Complete binary tree stored as an array. Max-heap: parent >= children. Min-heap: parent <= children. O(log n) insert, O(log n) extract-min/max, O(1) peek. Used for priority queues.

Heap property maintenance. Sift-up after insert, sift-down after extract. Floyd's build-heap is O(n), not O(n log n) -- a non-obvious result from the geometric series of sift-down costs at each level.

3.7 -- Graphs

Representation. Adjacency list: O(V + E) space, O(degree) edge lookup. Adjacency matrix: O(V^2) space, O(1) edge lookup. List is better for sparse graphs, matrix for dense.

Key properties. Directed vs undirected, weighted vs unweighted, cyclic vs acyclic, connected vs disconnected, bipartite.

3.8 -- Tries

Prefix tree for string storage. Each edge represents a character. O(m) lookup where m is the key length, independent of the number of stored keys. Used for autocomplete, spell checking, IP routing tables.

Part 4 -- Algorithm Design Paradigms

4.1 -- Divide and Conquer

Pattern: Split the problem into independent subproblems of the same type, solve each recursively, combine the results.

Examples: Merge sort, quicksort, binary search, Strassen's matrix multiplication, closest pair of points.

Recurrence analysis. The Master Theorem handles recurrences of the form T(n) = aT(n/b) + f(n). Three cases based on the relationship between f(n) and n^(log_b a).

4.2 -- Greedy Algorithms

Pattern: At each step, make the locally optimal choice. Never reconsider.

When it works. When the problem has the greedy choice property (a locally optimal choice leads to a globally optimal solution) AND optimal substructure.

Examples: Dijkstra's shortest path, Huffman coding, Kruskal's and Prim's MST algorithms, activity selection.

When it fails. The 0/1 knapsack problem -- greedy by value-to-weight ratio does not guarantee optimal packing. Use dynamic programming instead.

4.3 -- Dynamic Programming

Pattern: Break the problem into overlapping subproblems. Solve each subproblem once, store the result, and reuse it.

Two approaches. Top-down (memoization): recursive with caching. Bottom-up (tabulation): iterative, filling a table from base cases.

Identifying DP problems. Two signals: (1) optimal substructure -- the optimal solution contains optimal solutions to subproblems, and (2) overlapping subproblems -- the same subproblem is solved multiple times.

Classic examples. Fibonacci (trivial), longest common subsequence, edit distance (Levenshtein), 0/1 knapsack, matrix chain multiplication, shortest paths (Floyd-Warshall, Bellman-Ford).

State definition is the key insight. The hardest part of DP is defining what the subproblem is. For the knapsack problem: dp[i][w] = maximum value achievable using items 1..i with capacity w. For edit distance: dp[i][j] = minimum edits to transform the first i characters of string A into the first j characters of string B.

4.4 -- Backtracking

Pattern: Build a solution incrementally, abandoning a candidate ("backtracking") as soon as it is determined to be unviable.

Examples: N-queens, Sudoku solver, constraint satisfaction, generating permutations and combinations.

Pruning. The power of backtracking comes from pruning -- cutting off branches of the search tree that cannot lead to valid solutions. Without pruning, backtracking degenerates to brute-force enumeration.

Data Structure Selection Heuristic

Need	Structure	Why
Fast lookup by key	Hash table	O(1) average
Ordered iteration	Balanced BST / sorted array	O(n) in-order traversal
Fast min/max extraction	Heap	O(log n) extract, O(1) peek
LIFO access	Stack	O(1) push/pop
FIFO access	Queue	O(1) enqueue/dequeue
Prefix matching	Trie	O(m) per query, independent of n
Graph connectivity	Adjacency list + BFS/DFS	O(V + E) traversal
Range queries	Segment tree / BIT	O(log n) query and update

Common Mistakes

Mistake	Why it fails	Fix
Confusing O and Theta	O is an upper bound, not a tight bound	Use Theta when the bound is tight
Ignoring constant factors	O(n) with a constant of 10^6 beats O(n^2) only for large n	Profile, don't just analyze asymptotically
Using linked list by default	Poor cache locality makes it slower than arrays in practice	Default to arrays; use linked lists only when pointer-based insertion is critical
Quicksort on adversarial input	Sorted or nearly-sorted input with naive pivot = O(n^2)	Use random pivot or introsort
Hash table without collision handling	Degraded to O(n) in worst case	Implement proper chaining or open addressing
Forgetting base cases in DP	Infinite recursion or wrong answers	Define and verify base cases before writing the recurrence
Off-by-one in binary search	Infinite loop or missed elements	State the loop invariant explicitly, test on small arrays

Cross-References

• knuth agent: Algorithm analysis with literate programming rigor. Primary agent for complexity proofs and algorithm selection.
• turing agent: Computability theory -- which problems are algorithmically solvable and which are not.
• hopper agent: Practical implementation in real programming languages and systems.
• dijkstra agent: Software design principles that guide algorithm implementation.
• programming-fundamentals skill: Variables, control flow, recursion -- prerequisites for implementing algorithms.
• computational-thinking skill: Abstraction and decomposition that precede algorithm design.

References

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd edition. Addison-Wesley.
• Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. 2nd edition. Addison-Wesley.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms. 4th edition. MIT Press.
• Sedgewick, R. & Wayne, K. (2011). Algorithms. 4th edition. Addison-Wesley.
• Skiena, S. S. (2020). The Algorithm Design Manual. 3rd edition. Springer.
• Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley.