Algorithms Reference

A scannable, presentation-ready reference for every algorithm and design paradigm the course covers. Use this page to look something up mid-interview or mid-lecture — for the teaching version of any row, follow its link.

The one big takeaway: almost every algorithm choice is a trade-off along three axes — time, space, and guarantees (stable? in-place? worst-case bound?). Memorizing names is useless; memorizing which axis you’re trading away is the whole skill.

Big O quick reference

Notation	Name	1,000,000 elements, roughly	Example
`O(1)`	Constant	1 step	hash lookup, array index
`O(log n)`	Logarithmic	~20 steps	binary search, balanced tree height
`O(n)`	Linear	1,000,000 steps	linear scan, single loop
`O(n log n)`	Linearithmic	~20,000,000 steps	merge sort, heap sort, Timsort
`O(n²)`	Quadratic	10¹² steps	nested loops, bubble/selection/insertion sort
`O(2ⁿ)`	Exponential	astronomically large	naive recursive Fibonacci, brute-force subsets
`O(n!)`	Factorial	never finishes	brute-force traveling salesman

Master table — searching

Algorithm	Best	Average	Worst	Space	Precondition	When to reach for it
Linear search	`O(1)`	`O(n)`	`O(n)`	`O(1)`	none	Data unsorted, or a one-off search not worth sorting for.
Binary search	`O(1)`	`O(log n)`	`O(log n)`	`O(1)` iterative	data sorted	Data is already sorted (or sorted once, searched many times).

Master table — sorting

Algorithm	Best	Average	Worst	Space	Stable?	In-place?	When to reach for it
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	yes	yes	Teaching only — never in production.
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	no	yes	Minimizes the number of swaps — useful when writes are expensive (e.g. flash memory).
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	yes	yes	Small `n`, or data that’s already almost sorted — this is why Timsort uses it as a subroutine.
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	yes	no	Guaranteed `O(n log n)` no matter what — critical for real-time systems and linked lists.
Quicksort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	no	yes	Fastest in practice for arrays with good cache locality — the default in many libraries’ internal engines.
Heap sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	no	yes	Guaranteed `O(n log n)` and `O(1)` space — when you can’t afford merge sort’s extra array.
Timsort	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	yes	no	What Python’s `sorted()` and Java’s `Arrays.sort()` for objects actually run — hybrid merge + insertion sort, exploits existing runs.

The one big takeaway: O(n log n) is the proven lower bound for any comparison-based sort (CLRS proves this with a decision-tree argument). If you ever see a claimed O(n) comparison sort, it’s a bug, not a breakthrough. Non-comparison sorts (counting sort, radix sort) can beat O(n log n) — but only by exploiting structure in the data (small integer range, fixed digit count).

Master table — graphs

Algorithm	Time	Space	What it answers	When to reach for it
BFS (breadth-first search)	`O(V + E)`	`O(V)`	Shortest path in an unweighted graph; level-order layers	“Fewest hops” questions — social network degrees of separation, shortest unweighted route.
DFS (depth-first search)	`O(V + E)`	`O(V)`	Reachability, cycle detection, topological order, connected components	Exploring a maze, detecting cycles, or as a building block for other graph algorithms.
Dijkstra’s algorithm	`O((V + E) log V)` with a binary heap	`O(V)`	Shortest path in a weighted graph with non-negative weights	GPS routing, network routing — any weighted “cheapest path” problem with no negative edges.
Topological sort	`O(V + E)`	`O(V)`	A valid linear ordering of a DAG (directed acyclic graph)	Build systems, course prerequisites, task scheduling — “what must happen before what.”

Common trap: BFS and DFS both run in O(V + E) — the difference is never speed, it’s what order you visit nodes in and what question that order answers. Reach for BFS when “shortest” matters; reach for DFS when “does a path exist at all” or “what’s the structure” matters.

Master table — design paradigms

Paradigm	Core idea	Typical complexity	Guarantees optimal?	When to reach for it
Brute force	Try every possibility	usually exponential or factorial	yes (by exhaustion)	Baseline for correctness; small `n`; when you need a reference answer to test a faster algorithm against.
Divide & conquer	Split into same-shaped subproblems, combine results	often `O(n log n)` (see Master Theorem)	yes, if base case + combine step are correct	Problem splits cleanly and subproblems don’t overlap — merge sort, binary search, quicksort.
Greedy	Make the locally-best choice at each step, never look back	often `O(n log n)` (usually dominated by a sort)	only when the problem has the greedy-choice property	Activity selection, Huffman coding, Dijkstra — always prove greedy is correct first (exchange argument), don’t assume it.
Dynamic programming	Cache/reuse overlapping subproblem results	often reduces `O(2ⁿ)` → `O(n)` or `O(n²)`	yes, if the problem has optimal substructure	Overlapping subproblems + optimal substructure — Fibonacci, knapsack, edit distance, longest common subsequence.
Backtracking	Build a solution incrementally, abandon (“prune”) a branch the moment it can’t work	worst case exponential, pruning cuts the real-world cost	yes (explores all valid branches)	Constraint satisfaction — N-Queens, Sudoku, generating permutations/subsets.

How to tell greedy from DP in an interview: ask “does my choice now depend on choices I haven’t made yet, or could two different early choices both lead to the same later subproblem?” If subproblems overlap, it’s DP. If the locally-best move is always safe and never needs revisiting, it’s greedy. When in doubt, DP is the safer default — greedy without a correctness proof is a bug waiting to be found by a code reviewer, human or AI.

Choosing an algorithm — decision flow

Is the data sorted (or can you afford to sort it once)? → binary search beats linear search every time after that.
Do you need a guaranteed worst case (real-time system, adversarial input)? → merge sort or heap sort, not quicksort.
Is the graph weighted? → Dijkstra, not BFS. Unweighted? → BFS is simpler and just as correct.
Do subproblems overlap? → dynamic programming. Don’t overlap but split cleanly? → divide & conquer.
Can a locally-best choice never be undone without breaking correctness? → prove it, then go greedy.
Is the search space small and constraints hard (must satisfy all of them)? → backtracking.
None of the above, and correctness matters more than speed right now? → brute force, then optimize once it’s proven correct.

Session map

Algorithm / technique	Key idea	Headline complexity	Session
Big O Analysis	The common tool for judging cost	—	1.3 & throughout
Linear Search	Check each element until found	`O(n)`	3.1
Binary Search	Halve the range — data must be sorted	`O(log n)`	3.1
Sorting	Comparison sorting, cost & stability	`O(n log n)` lower bound	3.1
Tree Traversal	Visit nodes pre/in/post-order	`O(n)`	2.3
Recursion / Divide & Conquer	Split into same-shaped subproblems	depends on call structure	3.2
DP / Memoization	Reuse overlapping subproblems	often `O(2ⁿ)` → `O(n)`	3.3
BFS / DFS	Systematic graph exploration	`O(V + E)`	3.3

Note: graphs, graph traversal, and DP are presented conceptually in this course — the focus is understanding the principles and judging solution quality, not memorizing every proof.

Going deeper

CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms, 4th ed. — the canonical reference for every algorithm on this page; ch. 6–9 for sorting, ch. 15 for DP, ch. 22–24 for graphs.
Skiena, The Algorithm Design Manual, 3rd ed. — best “which technique when” intuition, with war stories about real production failures from picking the wrong one.
Sedgewick & Wayne, Algorithms, 4th ed. — clean, tested implementations and empirical performance comparisons for every sort and graph algorithm here.
Kleinberg & Tardos, Algorithm Design — the best source for proving a greedy algorithm correct (exchange arguments) and for DP formulation discipline.
Roughgarden, Algorithms Illuminated (4-volume) — approachable rigor, pairs well with Stanford CS161; especially good on the Master Theorem for divide & conquer.
The Big-O Cheat Sheet — a companion single-page complexity chart, useful for a quick sanity check against this page.