Mathematical Foundations

A set is an unordered collection of distinct objects. We write \(x \in S\) to mean "\(x\) is an element of \(S\)" and \(x \notin S\) for the opposite.

The sigma notation \(\displaystyle\sum_{i=a}^{b} f(i)\) means "add up \(f(i)\) for each integer \(i\) from \(a\) to \(b\)":

\[\sum_{i=1}^{n} f(i) = f(1) + f(2) + f(3) + \cdots + f(n)\]

When we have two indices, we iterate over both. The QuickSort analysis uses:

\[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} f(i,j)\]

This means: for each \(i\) from 1 to \(n{-}1\), for each \(j\) from \(i{+}1\) to \(n\), add \(f(i,j)\). It sums over all pairs \((i,j)\) with \(i < j\).

These describe how a function grows as its input \(n \to \infty\):

• \(f(n) = O(g(n))\): \(f\) grows at most as fast as \(g\). There exist \(c > 0, n_0\) such that \(f(n) \leq c\,g(n)\) for all \(n \geq n_0\).
• \(f(n) = \Omega(g(n))\): \(f\) grows at least as fast as \(g\).
• \(f(n) = \Theta(g(n))\): \(f\) grows at exactly the same rate as \(g\) (both \(O\) and \(\Omega\)).

\(\log_b(x) = y\) means \(b^y = x\). In this course:

• \(\ln x = \log_e x\) — natural logarithm (base \(e \approx 2.718\))
• \(\log x\) — in CS typically means \(\log_2 x\); in analysis often \(\ln x\). The chapter uses both.

Since all logarithms differ by a constant factor, \(O(\log n) = O(\ln n) = O(\log_2 n)\).

A probability \(\Pr[E]\) (or \(\mathbb{P}[E]\)) is a number between 0 and 1 that describes how likely an event \(E\) is to occur:

• \(\Pr[E] = 0\) means the event never happens
• \(\Pr[E] = 1\) means the event always happens
• \(\Pr[\text{not } E] = 1 - \Pr[E]\) — the complement rule

A random variable (r.v.) \(X\) is a numerical outcome of a random experiment. It maps each outcome of the experiment to a number.

• Discrete: takes values in a countable set (e.g., \(\mathbb{N}\), \(\{0,1\}\)). Described by a probability mass function (PMF): \(p(k) = \Pr[X = k]\).
• Continuous: takes values in \(\mathbb{R}\) or an interval. Described by a probability density function (PDF) \(f(x)\) where \(\Pr[a \leq X \leq b] = \int_a^b f(x)\,dx\).

The expected value (or mean) of a discrete random variable \(X\) is the weighted average of its possible values:

\[\mathbb{E}[X] = \sum_{x} x \cdot \Pr[X = x]\]

Think of it as the "long-run average" if you repeat the experiment many times.

The variance measures how "spread out" a random variable is around its mean:

\[\text{Var}[X] = \mathbb{E}\!\left[(X - \mathbb{E}[X])^2\right]\]

Shortcut formula (very useful):

\[\boxed{\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2}\]

For an event \(E\), the indicator random variable is:

\[\mathbf{1}_E = \begin{cases} 1 & \text{if } E \text{ occurs} \\ 0 & \text{otherwise}\end{cases}\]

Crucially: \(\mathbb{E}[\mathbf{1}_E] = 1 \cdot \Pr[E] + 0 \cdot \Pr[\text{not }E] = \Pr[E]\).

Two events \(A\) and \(B\) are independent if:

\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\]

Random variables \(X\) and \(Y\) are independent if for all values \(x, y\):

\[\Pr[X = x \text{ and } Y = y] = \Pr[X = x] \cdot \Pr[Y = y]\]

The number of independent trials needed until the first success, where each trial succeeds with probability \(q\).

\[\Pr[X = k] = (1-q)^{k-1} \cdot q, \quad k = 1, 2, 3, \ldots\]

\[\mathbb{E}[X] = \frac{1}{q}\]

The \(n\)-th Harmonic number is:

\[H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\]

\[\ln n \leq H_n \leq \ln n + 1\]

More precisely, \(H_n = \ln n + \gamma + O(1/n)\) where \(\gamma \approx 0.5772\) is the Euler-Mascheroni constant. So \(H_n = \Theta(\log n)\).

A function \(f: \mathbb{R} \to \mathbb{R}\) is convex if for all \(x, y\) and \(\lambda \in [0,1]\):

\[f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y)\]

Visually: the function curves upward. Examples: \(x^2\), \(e^x\), \(|x|\). A function is concave if \(-f\) is convex (curves downward): e.g., \(\ln x\), \(\sqrt{x}\).

A permutation of \(\{1, 2, \ldots, n\}\) is a rearrangement: a bijection \(\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}\). There are \(n!\) permutations of \(n\) elements.

An integer \(i\) is a fixed point of permutation \(\pi\) if \(\pi(i) = i\) — the element stays in its original position.

A recurrence relation defines \(T(n)\) in terms of smaller values. Example from QuickSort:

\[T(n) = cn + \frac{2}{n}\sum_{k=0}^{n-1} T(k)\]

To solve it, we can convert to a differential equation.

Replace the discrete recurrence with a continuous version using Fact: for non-decreasing \(f\):

\[\int_0^n f(x)\,dx \leq \sum_{k=0}^{n} f(k) \leq \int_1^{n+1} f(x)\,dx\]

The continuous version \(T(x) = cx + \frac{2}{x}\int_0^x T(u)\,du\) leads to the ODE \(F'(x) = cx + \frac{2}{x}F(x)\), which is solvable in closed form.