Appendices

Formula sheet

Here is a reminder of some formulae. You may find them helpful for reading the course notes and completing the exercises.

The Taylor series expansion of a function \(f(x)\) about a point \(x=a\): \[\begin{eqnarray*} f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \ldots + \frac{f^{(n)}(a)}{n!}(x-a)^n + \ldots \end{eqnarray*}\] If \(a = 0\) then the expansion is known as a Maclaurin series.

\[\begin{eqnarray*} \begin{array}{lrcl} \mbox{Taylor series expanison about 0:}& \exp(x) &=& \sum_{n=0}^\infty \frac{x^n}{n!}\\ \mbox{Mercator series:} & \log(1+x) &=& \sum_{k=1}^\infty\frac{(-1)^{k+1}}{k}x^k; -1<x\leq1 \\ & \exp(x) &=& \lim_{n\rightarrow\infty}\left(1 + \frac xn\right)^n\\ & \frac{1}{1-r} &=&\sum_{i=1}^\infty r^{i-1} \end{array} \end{eqnarray*}\]

Asymptotic notation

Here is some notation that is useful for expressing some of the asymptotic relationships presented in this course.

Big-O notation
\(f(n) = O(g(n))\) means there are positive constants \(c\) and \(k\), such that \(0 \leq |f(n)| \leq cg(n)\) for all \(n\geq k\). The values of \(c\) and \(k\) must be fixed for the function \(f\) and must not depend on \(n\). Strictly, the character is the upper-case Greek letter Omicron, not the letter O, but who can tell the difference?

Informally, saying some equation \(f(n) = O(g(n))\) means it is less than some constant multiple of \(g(n)\). The notation is read, “f of n is big oh of g of n”.

Little-o notation
\(f(n) = o(g(n))\) means for all \(c > 0\), there exists some \(k > 0\) such that \(0 \leq |f(n)| < cg(n)\) for all \(n \geq k\). The value of \(k\) must not depend on \(n\), but may depend on \(c\). Strictly, the character is the lower-case Greek letter omicron.

Informally, saying some equation \(f(n) = o(g(n))\) means \(f(n)\) becomes insignificant relative to \(g(n)\) as \(n\) approaches infinity. The notation is read, “f of n is little o of g of n”.

\(\sim\), sim
\(f(x)\sim g(x)\) means \(lim_{x \rightarrow \infty} f(x)/g(x) = 1\). Informally, saying some equation \(f(n)\) similar to \(g(n)\) means it grows at the same rate as g(n).