Asymptotic analysis and recurrences (Algorithms)

Cheat sheets

ALG-02Cheat sheet1 pageIn a paid pack

Asymptotic Notation and Growth Rates

Formal definitions of O, Omega, Theta, little-o and little-omega with their constants c and n0; the limit test and when it is inconclusive; reflexive, symmetric, transpose and transitive properties; sum and product rules; the growth ladder from constants through logarithms, powers, exponentials and factorials; Stirling's formula and log n!; comparing functions by taking logarithms, with an ordering of eight functions checked by script and the crossover that makes small-n checks misleading; log bases versus exponent bases.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

ALG-03Cheat sheet1 pageIn a paid pack

Loop Counting, Cases and Space Complexity

Exact iteration counts for the loop shapes that appear in code questions (dependent bounds, doubling, halving, squaring, square-root bounds, harmonic and logarithmic inner loops, geometric nests, triple nests), each checked by simulation at n = 16 and n = 1000; the sums they reduce to; worst, best and average case with the linear search example; input size measured in bits and why that makes trial division exponential; space complexity, auxiliary versus total, and recursion stack depth for common algorithms.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

ALG-04Cheat sheet1 pageIn a paid pack

Recurrences and the Master Theorem

The master theorem for T(n) = aT(n/b) + f(n) with its three cases, the regularity condition and the extended case-2 form for polylog factors; the recurrences it does not cover; the recursion-tree method shown on the uneven split T(n/3) + T(2n/3) + n; substitution with the lower-order-term trick; change of variables for square roots; unrolling subtract-and-conquer recurrences; and a table of 20 solved recurrences, each checked numerically by script.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

Diagrams from ALG-04

Recursion tree for T(n) = T(n/3) + T(2n/3) + n: root n, children n/3 and 2n/3, grandchildren n/9, 2n/9, 2n/9, 4n/9; every full level sums to n; the left path reaches a leaf first, the right path later; the last levels sum to at most n. — Recursion tree with uneven split: full levels cost n each. Source: sheet ALG-04.