Formulas for CMSC 351

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

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

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

$f(n) = o(g(n))$ if $\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = 0$.

$f(n) = \omega(g(n))$ if $\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = \infty$.

$f(n) \sim g(n)$ if $f(n) = g(n) + o(g(n))$.

Logarithms.

$$\begin{eqnarray*} a & = & b^{\log_ba} \\ \log_c(ab) & = & \log_ca + \log_cb \ ... ...log_ba & = & \frac{1}{\log_ab} \\ a^{\log_bn} & = & n^{\log_ba} \end{eqnarray*}$$

Quadratic Formula.

$$ax^2 + bx + c = 0    \Rightarrow    x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

Stirling's Formula.

$$n! = \left( \frac{n}{e} \right)^n \sqrt{2\pi n}  (1 + \Theta(1/n))$$

Probability.

$$\mbox{E}[X] = \sum_x x \mbox{Pr}\{X = x\} ,       \mbox{Va... ... - \mbox{E}^2[X] ,       \sigma[X] = \sqrt{\mbox{Var}[X]} .$$

Summations.
Distribution law:

$$\left( \sum_{i=1}^m a_i \right) \left( \sum_{j=1}^n b_j \right) = \sum_{i=1}^m \left( \sum_{j=1}^n a_i b_j \right)$$

Interchanging order of summation:

$$\sum_{i=1}^m \sum_{j=1}^n a_{ij} = \sum_{j=1}^n \sum_{i=1}^m a_{ij}$$

Splitting range:

$$\sum_{k=1}^n a_k = \sum_{k=1}^r a_k + \sum_{k=r+1}^n a_k$$

Arithmetic series:

$$\sum_{k=1}^n k = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

Geometric series:

$$\sum_{k=0}^n x^k = 1 + x + + x^2 \cdots + x^n = \frac{x^{n+1}-1}{x-1}      x \ne 1$$

$$\sum_{k=0}^{\infty} x^k = \frac{1}{1-x}      x < 1$$

Harmonic series:

$$H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{n} = \sum_{k=1}^n\frac{1}{k} = \ln n + O(1)$$

Telescoping series:

$$\sum_{k=1}^{n} (a_k - a_{k-1}) = a_n - a_0$$

Products:

$$\prod_{k=1}^n a_k = a_1 a_2 \cdots a_n           \log \prod_{k=1}^n a_k = \sum_{k=1}^n \log a_k$$

Approximation by integrals:

$$\int_{m-1}^n f(x) dx \le \sum_{k=m}^n f(k) \le \int_{m}^{n+1} f(x) dx      \mbox{for $f(x)$ monotonically increasing}$$

$$\int_{m}^{n+1} f(x) dx \le \sum_{k=m}^n f(k) \le \int_{m-1}^{n} f(x) dx      \mbox{for $f(x)$ monotonically decreasing}$$

``Master Theorem'':

$$T(n) = \cases{ a T(n/b) + c n^d & $n > 1$ \cr f & $n = 1$}$$

implies

$$T(n) = \cases{ \left(f + \frac{c}{a b^{-d} - 1}\right) n^{\lo... ...d $} \cr n^d(f + c\log_b n) = \Theta(n^d\log_b n) & $a = b^d$}.$$