Part B: Practice with Big$-O$

Recall the definition of big$-$O notation:

We say that a function $f(n)=O(g(n))$ if there exist constants $c>0$ and $n_0>0$ such that

AAn$n_0,f(n)c*g(n).$

Question B$1$: for each statement below, prove that the statement is true by finding constants $c$ and $n_0$ that satisfy the definition of big$-$O notation.

$n=O(n^2)$

$1000n=O(n^2)$

What constitutes a sufficient argument to prove that your choices of $c$ and $n_0$ work? Give a more convincing argument than just plugging in a few values of $n!$

Part C: Practice with Big$-$

The definition of big$-$ notation is essentially the same as for big$-$O$,$ except that we replace upper bounds by lower bounds:

We say that a function $f(n)=(g(n))$ if there exist constants $c>0$ and $n_0>0$ such that

AAn$n_0,f(n)c*g(n).$

This is not obviously the "right" definition of big$-,$ because it is not the logical inverse of the definition for big$-$O$.$ However, it is an eminently practical definition $1$ because it implies that

$f(n)=(g(n))Longleftrightarrowg(n)=O(f(n)).$

$($Take a moment to think about how you would prove this claim.$)$ Hence, to prove an $$ statement like that on the left side, simply interchange $f$ and $g$ and prove the corresponding $O$ statement. For example, to show that $n^2=(an+b),$ it is enough to show that $an+b=O(n^2).$

Question C$1$: Rewrite each statement below into Big$-$O form.

$n^2=(5000)$

$n=(an+b)$