Sequences & Probability

Part 5 of 8 · Previous: Algebra · Index · Next: CS Notation

22. Sequence and recurrence notation

(a_{n})_{n \geq 0}

means:

a_{0}, a_{1}, a_{2}, \dots

T (n) = T (n - 1) + n

defines $T (n)$ using a smaller input.

A recurrence normally needs a base case:

T (0) = 0

Then:

T (1) = T (0) + 1 = 1

T (2) = T (1) + 2 = 3

Common algorithm recurrence:

T (n) = 2 T (n /2) + O (n)

This describes an algorithm that:

Notation	Informal meaning
$O (f (n))$	Grows no faster than $f (n)$ , up to a constant
$Ω (f (n))$	Grows at least as fast as $f (n)$
$Θ (f (n))$	Grows at the same asymptotic rate
$o (f (n))$	Grows strictly slower
$ω (f (n))$	Grows strictly faster
$f (n) \sim g (n)$	Their ratio approaches 1

T (n) = O (n^{2})

formally means that there exist constants $c > 0$ and $n_{0}$ such that:

T (n) \leq c n^{2}

for every:

n \geq n_{0}

Big-O is an upper bound, not automatically an exact bound.

T (n) = Θ (n^{2})

means both:

T (n) = O (n^{2})

and:

T (n) = Ω (n^{2})

Symbol	Meaning
$Pr (A)$ or $P (A)$	Probability of event $A$
$P (A ∣ B)$	Probability of $A$ , given $B$
$A ⊥ B$	$A$ and $B$ are independent
$E [X]$	Expected value of $X$
$Var (X)$	Variance of $X$
$σ (X)$	Standard deviation
$X \sim D$	$X$ follows distribution $D$
$X_{1}, \dots, X_{n} \sim iid D$	Independent, identically distributed samples

P (A ∣ B) = \frac{P ( A \cap B )}{P ( B )}

Read:

Probability of $A$ , knowing that $B$ occurred.

For a discrete random variable:

E [X] = x \sum x P (X = x)

This is a probability-weighted average, not necessarily a value that actually occurs.