Cheatsheet

One page, every formula. If something here is unclear, follow the link to its topic.

Logs & exponents

Details: Topic 0

Details: Topic 0

Induction: base case → hypothesis $S(k)$ → prove $S(k+1)$ by writing it as " $S(k)$ + new piece".
Contradiction: assume the opposite → derive something impossible → so the claim holds.
Contraposition: to prove $P \Rightarrow Q$ , prove $\neg Q \Rightarrow \neg P$ .
Loop invariant: Initialization · Maintenance · Termination (substitute the exit value, e.g. $i = n + 1$ ).
Correctness = partial correctness + termination.

	Best	Worst	Extra space	Stable
Insertion sort	$\Theta(n)$ sorted	$\Theta(n^2)$ reverse	$\Theta(1)$	yes
Merge sort	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n)$	yes
Binary search	$\Theta(1)$	$\Theta(\log n)$	$\Theta(1)$ iterative	—

Insertion sort worst case: shifts $= \frac{n(n-1)}{2}$ . Shifts = number of inversions.
Merging lists of sizes $p$ and $q$ : at most $p + q - 1$ comparisons.

Details: Topic 5

Pattern	Θ
independent nested $n \times n$	$n^2$
`j ← 1 to i` inside `i ← 1 to n`	$n^2$ (≈ $n^2/2$ )
counter doubles / halves	$\log n$
halving outer, inner does $i$ work	$n$
header `for i ← 1 to n` runs	$n + 1$ times

Details: Topic 6

$f = O(g)$ : $\exists c, n_0$ with $f(n) \le c\,g(n)$ for all $n \ge n_0$
$f = \Omega(g)$ : $\exists c, n_0$ with $f(n) \ge c\,g(n)$ for all $n \ge n_0$
$f = \Theta(g)$ : both, i.e. $c_1 g \le f \le c_2 g$
$1 < \log n < \sqrt n < n < n\log n < n^2 < n^3 < 2^n < n! < n^n$
Disprove $f = O(g)$ : assume $c, n_0$ exist, derive $n \le$ constant, contradiction.

Details: Topic 8

For $T(n) = aT(n/b) + f(n)$ : level $i$ has $a^i$ nodes of size $n/b^i$ , there are $\log_b n + 1$ levels, and the leaves number $n^{\log_b a}$ .