Exam Practice

$t(n) \in O(g(n))$ means $t(n) \le c \cdot g(n)$ for all $n \ge n_0$. Represents an asymptotic upper bound.

$t(n) \in \Omega(g(n))$ means $t(n) \ge c \cdot g(n)$ for all $n \ge n_0$. Represents an asymptotic lower bound.

$t(n) \in \Theta(g(n))$ means $c_1 \cdot g(n) \le t(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$. Represents an asymptotically tight bound.

The most significant operation executed in the innermost loop that contributes most to total running time.

Algorithm to list all primes up to $n$ by iteratively marking multiples of each prime $p$ starting at $p^2$. Runs in $\Theta(n \log \log n)$ time.

$T(n) = 2T(n-1) + 1$ with $T(1) = 1$. Requires exactly $2^n - 1$ disk moves.

The smallest convex polygon enclosing a given set of points. The vertices of this polygon are extreme points.

Assigning $n$ people to $n$ jobs with an $n \times n$ cost matrix has $n!$ candidate permutations; exhaustive search takes $\Theta(n!)$ time.

An integer in a directed permutation that points to an immediately adjacent neighbor with a strictly smaller value.

For $T(n) = aT(n/b) + \Theta(n^d)$: $\Theta(n^d)$ if $a < b^d$; $\Theta(n^d \log n)$ if $a = b^d$; $\Theta(n^{\log_b a})$ if $a > b^d$.

Multiplies two $n$-digit numbers using 3 recursive half-size multiplications instead of 4, running in $\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$.

Merge Sort is stable with guaranteed $\Theta(n \log n)$ and $\Theta(n)$ extra space. Quick Sort is in-place and faster on average, but has $\Theta(n^2)$ worst case.