amortized-recurrence-analysislisted
Install: claude install-skill rustcircle/c101
# Amortised and recurrence analysis
Bounds with their model, measure and proof. Algorithm design is in `algorithm-design-paradigms`,
Chernoff-style high-probability bounds in `randomized-algorithms-sketches`, benchmarking
statistics in `performance-optimization`; hub `cs-foundations` section 2.
## 1. Declare the model and the measure first
| Model | Unit cost | Use |
|---|---|---|
| word RAM, w = Theta(log n) bits | arithmetic, memory access on w-bit words | default for algorithms on integers and pointers |
| comparison | comparisons only | sorting and searching lower bounds |
| external memory (B, M) | block transfers of B items, memory M | databases, large sorts: sort(N) = Theta((N/B) log_{M/B}(N/B)) |
| work-span | work W (total ops), span D (critical path) | parallel algorithms, T_p <= W/p + D |
| Measure | Statement | Typical source |
|---|---|---|
| worst case | every input of size n | deterministic code paths |
| expected | over the algorithm's own randomness, every input | quicksort with random pivots, hashing with random seeds |
| average | over a stated input distribution | uniform keys: say so explicitly |
| amortised | total over any sequence divided by its length | dynamic arrays, union-find, splay trees |
| with high probability | probability >= 1 - n^(-c) | skip lists, randomised load balancing |
Hidden costs: hashing is O(1) only in expectation and with a suitable hash; big integers cost
O(digits) per operation; string comparison and hashing cost O(length