Chapter 3: Growth Functions

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001

The basics of proving and comparing computational runtimes.

3.1 Asymptotic Notation

$\Theta$-notation:

Big theta is an asymptotically tight bound.

$\Theta(g(n))$ = $\{f(n)$ : there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$

$O$-notation:

Big O is an asymptotic upper bound, a.k.a. the worst-case running time.

$O(g(n))$ = $\{f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0\}$

$\Omega$-notation:

Big omega is an asymptotic lower bound, a.k.a. the best-case running time.

$\Omega(g(n))$ = $\{f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0\}$.

Theorem 3.1

For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

3.2 Standard Notations and Common Functions

A function $f(n)$ is monotonically increasing if $m \leq n$ implies $f(m) \leq f(n)$. Similarly, it is monotonically decreasing if $m \leq n$ implies $f(m) \geq f(n)$. A function $f(n)$ is strictly increasing if $m \lt n$ implies $f(m) \lt f(n)$ and strictly decreasing if $m \lt n$ implies $f(m) \gt f(n)$.

Exponential Identities:

$(a^m)^n = a^{mn}$

$(a^m)^n = (a^n)^m$

$a^ma^n = a^{m+n}$

Logarithmic Identities:

For all real $a \gt 0$, $b \gt 0$, $c \gt 0$, and $n$,

$a = b^{log_ba}$

$log_c(ab) = log_ca + log_cb$

$log_ba^n = nlog_ba$

$log_ba = \frac{log_ca}{log_cb}$

$log_b(1/a) = -log_ba$

$log_ba = \frac{1}{log_ab}$

$a^{log_bc} = c^{log_ba}$

Fibonacci Numbers:

e.g. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, $\dots$

The closed form, based on the golden ratio:

$\phi = \frac{1 + \sqrt5}{2}$

and its inverse:

$\hat\phi = \frac{1 - \sqrt5}{2}$

is:

$F_i = \frac{\phi^i - \hat\phi^i}{\sqrt5}$