\documentstyle[11pt,fullpage]{article}
\pagestyle{empty}
\begin{document}

\begin{center}Formulas for CMSC 251
\end{center}
{\bf 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))$.
%\\ \\

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

{\bf Quadratic Formula.}
\[
ax^2 + bx + c = 0
~~ \Rightarrow ~~~
x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}
\] \\

{\bf Stirling's Formula.}
\[
n! ~\approx~ \left( \frac{n}{e} \right)^n \sqrt{2\pi n}
\]

%\newpage

{\bf Probability.}
\[
\mbox{E}[X] = \sum_x x \mbox{Pr}\{X = x\} ~,
	~~~~~ \mbox{Var}[X] = \mbox{E}[(X - \mbox{E}(X))^2]
		= \mbox{E}[X^2] - \mbox{E}^2[X] ~,
	~~~~~ \sigma[X] = \sqrt{\mbox{Var}[X]} ~.
\]

%\newpage
{\bf 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}
\]

%{\bf Recurrences}
\bigskip
``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^{\log_b a}
 - \frac{c n^d}{a b^{-d} - 1} 
= \cases{\Theta(n^{\log_b a}) & $ a > b^d $ \cr
         \Theta(n^d) & $ a < b^d $} \cr
n^d(f + c\log_b n) = \Theta(n^d\log_b n) & $a = b^d$}.\]


\end{document}
