← ClaudeAtlas

amortized-recurrence-analysislisted

Proving running-time bounds: cost models and measures (worst, expected, amortised, average, w.h.p.), recurrences (master theorem and its gaps, Akra-Bazzi, recursion trees, substitution, characteristic roots), aggregate, accounting and potential methods with standard potentials, de-amortisation for latency, competitive analysis, work-span bounds and empirical scaling checks. Load when deriving, proving or disputing a complexity bound.
rustcircle/c101 · ★ 0 · AI & Automation · score 65
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