Algorithm Design and Analysis
Core concepts, formulas and conditions at a glance.
See the learning route first
Follow the arrows. Choose a stage to open its first lesson. The full framework lists every topic.
- 01
Specify algorithms and choose supporting structures
Begin with correctness and cost. Choose storage from the operations that searching, ordering and updates require.
10 topics ↗ - 02
Traverse and optimize networks
Model connections, then distinguish reachability, shortest routes and the cheapest connecting network.
5 topics ↗ - 03
Prove greedy choices
Identify the safe local decision and a lower bound or exchange argument that certifies the whole result.
3 topics ↗ - 04
Divide problems and analyze uncertainty
Track recursive subproblems, control pivot and random choices, and measure input size honestly.
8 topics ↗
01 / Name the guarantee
Worst-case maximizes over inputs; expected averages over stated randomness; amortized averages over a sequence. Input size and arithmetic cost model must be explicit before interpreting any bound.
02 / Representation tradeoffs
Array indexing is O(1), interior shifts O(n). Doubly linked edits at known positions are O(1), but locating an index is O(n). Include both search and modification costs.
03 / BST versus AVL
BST search and update cost O(h); range reporting costs O(h+k). AVL maintains child-height difference at most one, ensuring h=O(log n). k is output size.
04 / Heap priorities
A min-heap keeps each parent no larger than its children. Minimum is O(1); insert and remove-min are O(log n). A heap array is not fully sorted.
05 / Hash-table assumptions
With suitable uniform hashing, chaining lookup is expected O(1+α), α=n/m. Linear probing needs tombstones or cluster repair after deletion. Cuckoo insertion can trigger expensive rebuilding.
06 / Graph traversals
Adjacency-list BFS and DFS cost O(n+m). BFS minimizes edge count. Undirected DFS tree edge (u,v) is a bridge when low[v]>disc[u], with parent edges handled correctly.
07 / Path versus tree
Dijkstra relaxes d[u]+w(u,v) and requires nonnegative weights. Prim uses w(u,v) to connect a new vertex. MSTs minimize total network weight, not source-to-vertex distances.
08 / Greedy proof certificates
Fractional knapsack uses density and equal-weight exchange. Interval partitioning matches overlap depth. Huffman combines two minimum frequencies. Each proof depends on its specific feasible-choice structure.
09 / Recurrences
T(n)=T(n/2)+Θ(1) gives Θ(log n); 2T(n/2)+Θ(n) gives Θ(n log n); 3T(n/2)+Θ(n) gives Θ(n^log₂3). Include split and combination costs.
10 / Sort versus select
Randomized quicksort sorts both sides in expected O(n log n). Quickselect follows one side in expected O(n). Both can take Θ(n²) on unlucky pivot sequences.
11 / Random structures
Fisher–Yates chooses j uniformly in {0,…,i} before fixing position i. Skip-list promotion probability one half gives expected O(log n) operations and expected O(n) storage.
12 / Read the input length
For q encoded in k≈log₂q bits, √q≈2^(k/2). A polynomial in the numerical value may be exponential in bit length; this distinction matters for cryptographic complexity.