# ALGORITHMS.md - Algorithms & Data Structures
**Authority:** guidance (algorithm selection, complexity analysis, and optimization)
**Layer:** Guides
**Binding:** No
**Scope:** algorithm patterns, complexity trade-offs, and data structure selection
**Non-goals:** academic proofs, premature optimization without measurement
---
## 1. Algorithm Selection Principles
### 1.1 Measure First, Optimize Second
**Premature optimization is the root of all evil.**
- Profile before optimizing
- Optimize bottlenecks, not everything
- Constant factors matter in practice
- Cache efficiency > Big-O for small n
### 1.2 The Right Data Structure
**Programs = Algorithms + Data Structures**
- Algorithm choice depends on data structure
- Data structure choice depends on access patterns
- Space-time trade-offs
- Cache-friendly vs cache-oblivious
### 1.3 Practical vs Theoretical
- **Big-O:** Asymptotic behavior
- **Cache:** Memory hierarchy matters
- **Parallelism:** Amdahl's Law limits
- **Constants:** 2× slower is still O(n)
### 1.4 Production Mindset
The gap between academic algorithm knowledge and production engineering is real:
- **Standard libraries first:** Most business value lives in domain logic, not sorting internals. Use language-native, battle-tested implementations. Custom algorithms are warranted only when the standard approach imposes a measurable, load-bearing bottleneck.
- **Maintenance cost is a first-class constraint:** A clever algorithm maintained by one person is a single point of failure. Favor correct and readable over theoretically optimal.
- **Data locality beats asymptotic complexity for small n:** Most production operation sets are small (n < 1000). O(n²) with cache-friendly sequential access frequently outperforms O(n log n) with pointer chasing. The memory wall is the real bottleneck in modern hardware.
- **Prefer scale-out over scale-up:** An O(n log n) algorithm that parallelizes cleanly across 100 machines is often more practical than an O(n) algorithm that must remain single-threaded.
- **Determinism is a correctness property:** In a system governed by reproducible validation, algorithms must produce identical output for identical input. Avoid non-deterministic choices (e.g., unseed random pivots) anywhere output is compared or stored.
- **Resource budgets are not optional:** Every algorithm must have time and memory bounds enforced at the call site. An algorithm that may run forever or allocate without limit is a bug, not a performance risk.
---
## 2. Complexity Analysis
### 2.1 Time Complexity
| O(1) | Constant | Unlimited | Hash map access |
| O(log n) | Logarithmic | Millions | Binary search |
| O(n) | Linear | Billions | Single loop |
| O(n log n) | Linearithmic | Millions | Sorting |
| O(n²) | Quadratic | Thousands | Nested loops |
| O(2ⁿ) | Exponential | < 30 | Brute force |
| O(n!) | Factorial | < 12 | Permutations |
### 2.2 Space Complexity
- **In-place:** O(1) extra space
- **Linear:** O(n) space
- **Recursion:** Call stack depth
- **Cache:** Working set size
### 2.3 Amortized Analysis
- **Average case:** Over sequence of operations
- **Example:** Dynamic array doubling (amortized O(1) append)
- **Worst case:** Single operation cost
---
## 3. Fundamental Algorithms
### 3.1 Searching
**Linear Search:**
- O(n) time, O(1) space
- Unsorted data, small datasets
**Binary Search:**
- O(log n) time, O(1) space
- Sorted data, random access
- Variants: lower_bound, upper_bound
**Hash-based Lookup:**
- O(1) average, O(n) worst
- Unsorted data, unique keys
- Trade-off: space for time
### 3.2 Sorting
**Comparison Sorts:**
- **Quicksort:** O(n log n) avg, O(n²) worst, in-place
- **Mergesort:** O(n log n), stable, not in-place
- **Heapsort:** O(n log n), in-place, not stable
- **Timsort:** O(n log n), adaptive, stable (Python, Java)
**Non-Comparison Sorts:**
- **Counting sort:** O(n + k), integer keys
- **Radix sort:** O(nk), integer keys
- **Bucket sort:** O(n), uniform distribution
**When to use what:**
- Default: Language's built-in sort (optimized)
- Large datasets: External sort
- Nearly sorted: Insertion sort, Timsort
- Linked lists: Mergesort
### 3.3 Graph Algorithms
**Graph Representations:**
- **Adjacency matrix:** O(V²) space, fast edge lookup
- **Adjacency list:** O(V + E) space, sparse graphs
**Traversal:**
- **BFS:** Shortest path (unweighted), level-order
- **DFS:** Topological sort, cycle detection, connected components
**Shortest Path:**
- **Dijkstra:** Single source, non-negative weights, O((V + E) log V)
- **Bellman-Ford:** Single source, negative weights, O(VE)
- **Floyd-Warshall:** All pairs, O(V³)
- **A*:** Heuristic-guided, pathfinding
**Minimum Spanning Tree:**
- **Kruskal:** O(E log E), edge list
- **Prim:** O(E log V), adjacency list
---
## 4. Data Structures
### 4.1 Arrays and Lists
**Arrays:**
- O(1) random access
- O(n) insert/delete
- Cache-friendly
**Linked Lists:**
- O(n) random access
- O(1) insert/delete (known position)
- Poor cache locality
**Dynamic Arrays (Vector/ArrayList):**
- Amortized O(1) append
- O(n) worst case (resize)
- Most practical choice
### 4.2 Stacks and Queues
**Stack (LIFO):**
- Push, pop: O(1)
- Use: DFS, expression evaluation, undo
**Queue (FIFO):**
- Enqueue, dequeue: O(1)
- Use: BFS, task scheduling, buffering
**Deque:**
- Double-ended operations
- O(1) at both ends
**Priority Queue:**
- Insert: O(log n)
- Extract-min/max: O(log n)
- Heap implementation
### 4.3 Trees
**Binary Search Tree (BST):**
- O(log n) avg, O(n) worst (unbalanced)
- In-order traversal = sorted
**Balanced BSTs:**
- **AVL:** Strictly balanced, faster lookups
- **Red-Black:** Loosely balanced, faster inserts
- **B-Trees:** Optimized for disk, databases
**Heaps:**
- Complete binary tree
- Min-heap or max-heap
- Priority queue implementation
- Heapify: O(n)
**Tries (Prefix Trees):**
- String storage
- O(m) lookup (m = string length)
- Autocomplete, spell check
### 4.4 Hash Tables
- O(1) average lookup
- O(n) worst case (collisions)
- Load factor determines performance
- Collision resolution: chaining vs open addressing
### 4.5 Graph Representations
- **Adjacency matrix:** Dense graphs
- **Adjacency list:** Sparse graphs
- **Edge list:** Kruskal's algorithm
---
## 5. Advanced Algorithms
### 5.1 Dynamic Programming
**When to use:**
- Optimal substructure
- Overlapping subproblems
- Can be memoized or tabulated
**Examples:**
- Fibonacci
- Knapsack
- Longest Common Subsequence
- Edit Distance
- Matrix Chain Multiplication
**Approaches:**
- **Top-down:** Recursion + memoization
- **Bottom-up:** Iterative tabulation
### 5.2 Greedy Algorithms
**When to use:**
- Greedy choice property
- Optimal substructure
- Local optimum = global optimum
**Examples:**
- Dijkstra's algorithm
- Huffman coding
- Activity selection
- Fractional knapsack
### 5.3 Divide and Conquer
**Pattern:**
1. Divide problem into subproblems
2. Conquer subproblems recursively
3. Combine solutions
**Examples:**
- Mergesort
- Quicksort
- Binary search
- Strassen's matrix multiplication
- Fast Fourier Transform (FFT)
### 5.4 Backtracking
**When to use:**
- Search all possible solutions
- Constraint satisfaction
- Can prune invalid branches
**Examples:**
- N-Queens
- Sudoku solver
- Subset sum
- Graph coloring
---
## 6. Probabilistic Data Structures
### 6.1 Bloom Filter
- **Space:** O(n), n = expected elements
- **Time:** O(k), k = hash functions
- **Use:** Membership testing, cache filtering
- **Trade-off:** False positives possible, no false negatives
### 6.2 HyperLogLog
- **Space:** O(1), ~1.5KB
- **Time:** O(1) per element
- **Use:** Cardinality estimation
- **Accuracy:** ~2% error
### 6.3 Count-Min Sketch
- **Space:** O(w × d), w = width, d = depth
- **Time:** O(d) per operation
- **Use:** Frequency estimation
- **Trade-off:** Overestimates possible
### 6.4 Skip List
- **Time:** O(log n) average
- **Space:** O(n)
- **Use:** Ordered set/map, simpler than BST
- **Benefits:** Lock-free implementations possible
### 6.5 T-Digest
- **Space:** O(1), configurable accuracy
- **Time:** O(1) per observation
- **Use:** Percentile estimation
- **Accuracy:** High accuracy at tails
---
## 7. Algorithm Patterns
### 7.1 Two Pointers
- **Use:** Sorted arrays, palindromes, sliding window
- **Time:** O(n)
- **Space:** O(1)
### 7.2 Sliding Window
- **Use:** Subarray problems, string processing
- **Time:** O(n)
- **Variants:** Fixed size, variable size
### 7.3 Fast and Slow Pointers
- **Use:** Cycle detection (Floyd's algorithm)
- **Time:** O(n)
- **Space:** O(1)
### 7.4 Merge Intervals
- **Use:** Overlapping intervals, scheduling
- **Time:** O(n log n)
- **Pattern:** Sort, then merge
### 7.5 Cyclic Sort
- **Use:** Arrays with values in range [1, n]
- **Time:** O(n)
- **Space:** O(1)
### 7.6 Topological Sort
- **Use:** Dependency ordering, task scheduling
- **Time:** O(V + E)
- **Algorithm:** Kahn's or DFS-based
---
## 8. Optimization Strategies
### 8.1 Space Optimization
- **In-place:** Modify input instead of copy
- **Bit manipulation:** Compact representation
- **Streaming:** Process data in chunks
### 8.2 Time Optimization
- **Memoization:** Cache results
- **Precomputation:** Compute once, use many
- **Early exit:** Fail fast
- **Pruning:** Skip unnecessary work
### 8.3 Parallel Optimization
- **Map-Reduce:** Distributed processing
- **SIMD:** Vectorized operations
- **GPU:** Massive parallelism
---
## 9. Anti-Patterns
- **Premature optimization:** Optimize without profiling
- **Wrong data structure:** Array for frequent inserts
- **O(n²) when O(n log n) possible:** Nested loops on sorted data
- **Brute force:** When DP or greedy applies
- **Ignoring cache:** Linked lists for sequential access
- **Recursion without base case:** Stack overflow
- **Unbounded recursion:** Convert to iteration
- **No early termination:** Continue when answer found
- **Recomputing values:** No memoization
- **Over-engineering:** Complex algorithm for simple problem
---
## Links
- `methodology/ARCHITECTURE.md` - binding architecture doctrine
- `architecture/MEMORY.md` - Memory and cache efficiency
- `architecture/CONCURRENCY.md` - Parallel algorithms
- `architecture/PERFORMANCE.md` - Performance optimization