Let $f(n) = 2n^2 + 7n − 1$. Show that $f = O(n^3)$

Question

The book I'm using states that a function $f$ is $O(g)$ if there exists a positive constant $C$ and a positive integer $k$ such that $$f(n)\le Cg(n)$$ for every integer $n\ge k$.

How do I use the definition to solve this problem?

Answer 1

since n is positive, $ cn \leq cn^2 \leq cn^3$ for every $c \in \mathbb{N}$

therefore:

$ f(n) = 2n^2+7n−1 \leq 2n^2+7n \leq 2n^3 + 7n^3 = 9n^3$

So obviously:

$f(n) = O(n^3)$

Answer 2

Take $C=1$ and find such $k$ that $f(n)\leqslant g(n)$ for all $n> k$: $$2n^2+7n-1\leqslant n^3$$ $$n^3-2n^2-7n+1\geqslant 0$$

Substitute $n=m+4$: $$(m+4)^3-2(m+4)^2-7(m+4)+1\geqslant 0$$ $$m^3+10m^2+25m+5\geqslant 0$$ Function above is clearly positive for $m>0\implies n-4>0\implies n>4$, thus $k=4$.

---

Another solution:

$$\lim_{n\to\infty}\frac{2n^2+7n-1}{n^3}=0$$ It implies that $f(n)\in O(n^3)$