3

Here is the problem and proof given by my book:

Prove the function $f(n) = 12n^{2}+6n$ is o($n^{3}$)

Let us first show that $f(n)$ is o($n^{3}$)

Let $c \gt 0$ be any constant. If we take $${n_{0}}={{{(12+6)}\over {c}}} ={ {18}\over{c}}$$, then $18\le cn$, for $n\ge n_{0}$.

Thus, if $n\ge n_{0}$, $f(n)=12n^{2}+6n \le 12n^{2}+6n^{2}=18n^{2}≤cn^{3}$.


Definiton of Little Oh:

$f(n) = \circ (g(n))$ means for all $c > 0$ there exists some $n_{0}> 0$ such that $0 \le f(n) \lt cg(n)$ for all $n \ge n_{0}$. The value of $n_{0}$ must not depend on $n$, but may depend on $c$.


What I don't understand:


How was $n_{0}$ determined to be ${(12+6)}\over{c}$ =$ {18}\over{c}$ $?$
Where did $12n^{2}+6n^{2}$ in $f(n)=12n^{2}+6n \le 12n^{2}+6n^{2}=18n^{2}\le cn^{3}$ come from?

Chiranjeev_Kumar
  • 3,061
  • 16
  • 30
yako
  • 311

1 Answers1

5

With proofs like these, you have to think forward and then backward, typically. We're interested in determining $n_0$ for $c>0$ such that for all $n\ge n_0$ we get $$0\le 12n^2+6n\le cn^3$$ Consider that we know that $n^2\ge n$, so it follows we can bound: $$n\le n^2\\6n\le 6n^2\\12n^2+6n\le 12n^2+6n^2\\f(n)\le 18n^2$$

Now, we want to find some $n_0$ such that $f(n)\le cn^3$. Notice that the upper bound we've found for $f$ is easier to work with than $f$ itself, so if we can find $n_0$ so that $18n^2\le cn^3$ for all $n>n_0$ then it follows this $n_0$ works for $f$ as well, since $$f(n)\le 18n^2\le cn^3\\\implies f(n)\le cn^3$$

Using the upper bound $18n^2$ instead we see: $$18n^2\le cn^3\\cn^3-18n^2\ge 0\\n^2(cn-18)\ge 0$$Since $n^2\ge 0$ we require $cn-18\ge 0\Leftrightarrow n\ge\frac{18}c$, so we can choose $n_0=\frac{18}c$ and we are done.

Note this is not the tightest lower bound for $n$ such that $f(n)\le cn^3$, but this doesn't matter, since we are focused solely on showing that $n^3$ dominates eventually -- as long as we find some $n_0$, we are okay.

obataku
  • 5,571
  • 2
    If little oh is concerned with ssaying that one function is strictly less than than another asymptotically then why are we saying f(n) ≤ cg(n) and not f(n) < cg(n)? – yako Sep 01 '15 at 15:29
  • if for any $c$ we can find $n_0$ such that $0\le f(n)\le cg(n)$ holds for $n\ge n_0$ then it follows that $n\ge n_0$ is sufficient to give a strict bound $0\le f(n)<dg(n)$ for $d>c$. So if we want to show for $d$ that there is $n_0$ so that $0\le f(n)< dg(n)$ for $n\ge n_0$, just pick a $c$ such that $0<c<d$ (e.g. $c=d/2$) and $n_0=\frac{18}c=\frac{36}d$ will work for the strict inequality in $d$. – obataku Sep 01 '15 at 15:43