Standard 2: Big-O and Complexity 2: Proofs

Short description: Prove statements of the form f = O(g).

Relevant notes: Topic A: Big-O Notation and Complexity.

Full description

Given a pair of functions f(n) and g(n), prove that f = O(g) using either a C,N proof or a limit proof as requested or as appropriate.

Example problem

Part a. Let $f(n) = 8n^3 + 3$ and $g(n) = n^4$. Give a $C,N$ proof that $f = O(g)$.

Part b. Let $f(n) = \log(n + 1)$ and let $g(n) = n$. Give a limit proof that $f = O(g)$.

Sample Solution

Part a.

We choose $C=11,N=1$. For all $n \geq 1$, we have $1 \leq n^3$ and we also have $n^3 \leq n^4$. Using these facts, for $n \geq 1$,

\begin{align*} 8n^3 + 3 &\leq 8n^3 + 3n^3 \\ &= 11n^3 \\ &\leq 11n^4 . \end{align*}

We have proven, for $n \geq 1$, that $f(n) \leq 11 g(n)$.

Part b.

We will prove that $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$. Both $f$ and $g$ tend to infinity, so we can apply L'Hopital's rule. We have that $\frac{df}{dn} = \frac{1}{n+1}$ and $\frac{dg}{dn} = 1$. Therefore,

\begin{align*} \lim_{n \to \infty} \frac{f(n)}{g(n)} &= \lim_{n \to \infty} \frac{\log(n+1)}{n} & \text{definitions of $f$ and $g$} \\ &= \lim_{n \to \infty} \frac{1/(n+1)}{1} & \text{L'Hopital's rule} \\ &= \lim_{n \to \infty} \frac{1}{n+1} \\ &= 0. \end{align*}

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing and proofs. For Part a, it should be a $C,N$ proof as defined in the notes. It should clearly state what constants are chosen for $C$ and $N$. It shoud use the constants correctly, e.g. mention that the inequalities it uses are true when $n \geq N$ and conclude that, under these conditions, $f(n) \leq C g(n)$.

For Part b, it should prove that $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$. It should correctly use L'Hopital's rule or another method of simplifying the limit.

4 (Pass, Near-Perfect): perfectly clear, no arithmetic mistakes, correct and well-justified steps, no excess writing.
3 (Pass, Proficient): clear, easy to follow, correct arithmetic, steps of proof are correct and justified, little to no excess writing or unnecessary scratch work.
2 (Fail, Progress): may have consequential arithmetic mistakes. For Part a, may not clearly state the choices of $C$ and $N$, or may apply those choices incorrectly. May make an incorrect claim or fail to justify a claim. May provide an incorrect justification for a step. May include scratch work or an explanation of how $C$ and $N$ were produced. For Part b, may not apply L'Hopital's rule correctly. May make an incorrect claim or fail to justify a claim. May provide an incorrect justification for a step. May include excess scratch work.
1 (Fail, Wrong Track): Part a: Does not follow the structure of a $C,N$ proof. Part b: Does not follow the structure of a limit proof.