Algorithms

An algorithm is a finite, well-defined sequence of steps that solves a problem. The right algorithm at scale can be the difference between milliseconds and hours.

Overview

Picking algorithms is mostly picking data structures first — the structure constrains what operations are cheap. After that, the cost model (memory access, cache behavior, I/O) often matters more than raw Big-O.

Complexity

• O(1) — constant (hash lookup, array index).
• O(log n) — binary search, balanced tree ops.
• O(n) — linear scan.
• O(n log n) — comparison-based sort, FFT.
• O(n²) — naive pairwise (bubble sort).
• O(2ⁿ), O(n!) — combinatorial; avoid for large n.
• Space matters too — recursion depth, auxiliary arrays.

Sorting

• Quicksort — O(n log n) avg, O(n²) worst; in place.
• Mergesort — O(n log n) worst; stable; O(n) extra.
• Heapsort — O(n log n); in place; not stable.
• Insertion sort — O(n²) but excellent on near-sorted / small n.
• Counting / radix — O(n + k); integer keys only.
• Timsort — hybrid; default in Python & Java.

Searching

• Linear search — O(n).
• Binary search — O(log n) on sorted data.
• Hashing — O(1) expected; collisions, load factor.
• BFS / DFS for graphs and trees.
• A* — heuristic-guided shortest path.

Graph Algorithms

• Dijkstra — shortest path, non-negative weights, O((V+E) log V).
• Bellman-Ford — handles negative edges, O(VE).
• Floyd-Warshall — all-pairs, O(V³).
• Kruskal / Prim — minimum spanning tree.
• Topological sort — DAGs, scheduling.
• Max flow — Edmonds-Karp, Dinic.

Design Paradigms

• Divide & conquer — mergesort, FFT, Karatsuba.
• Dynamic programming — overlapping subproblems + memoization.
• Greedy — locally optimal choices (when they work).
• Backtracking — DFS with pruning (SAT, N-queens).
• Branch & bound — for optimization.
• Randomized — Monte Carlo, Las Vegas.