Big Oh Notation

LaTeX in IPython Notebook

Markdown cells in IPython Notebook can process a subset of the LaTeX typesetting language (by far the most widely used method for typesetting mathematical writing). Here is a very nice quick reference with basic mathematics typesetting commands. Below is a mathematical proof using this LaTeX functionality.

Example

Claim: $\quad 3n^3 + 6n^2\log n - 7 = O(n^3)\qquad$ (as $n\to\infty$)

Note: In this class $\log$ refers to the natural logarithm, that is, the logarithm in base $e$ (sometimes also called $\ln$).

Proof

First, consider the function $f(n)=n-\log(n)$. Note that $f(1)=1$ and that $f'(n)=1-\frac{1}{n}$, so $f'(n)\ge 0$ for $n\ge 1$. Thus, $f(n)\ge f(1)=1$ for $n\ge 1$, which implies that $\log(n)\le n$ for $n\ge 1$. So, for $n\ge 1$, we have

which proves the claim.

Exercise

Prove that $n^2=O(2^n)$ as $n\to\infty$. Hint: First argue that if $n$ is large enough

Then apply the exponential function $e^x$ to both sides. You should be careful to check that the inequality remains valid when applying $e^x$.

1. The limit as n approaches infinity of n^2/2^n is zero. (L'Hopital)

2. n^2 is in o(2^n). (1 & demonstrated in class)

3. o(2^n) is a subset of O(2^n). (definitions of o and O)

4. n^2 is in O(2^n). (2 & 3 & transative property)