Prove that so and so is $O(x^4)$

Question

Given $f(x) = x^3 + 20x + 1$, how would I prove this is $O(x^4)$?

By definition, the function is $O(x^4)$ iff $f(x) <= cn^4$, where $c$ is some constant. However, I'm not sure where to go from here. I have the answer, but the methodology this site uses escapes me. It states that if the condition is true, then $\frac{1}{n} + \frac{20}{n^3} + \frac{1}{n^4} <= c$, but I've no idea where this came from.

I've tagged this as 'optimization' assuming it's relevant. This is for a computer sciences course (algorithms).

Answer 1

$f \in O(g)$ means that for sufficiently large $x$, $f(x) \le c\cdot g(x)$.

For your problem, you can actually pick any positive $c$, and eventually all $f(x)$ will be within the designated bound. For other functions, you might actually have to put some thought into finding a suitable $c$ value, but not with this one.

Try $c=1$ since it is simple enough.

$$x^4 \ge x^3 + 20x + 1$$

$$x > 3.106213639450556...$$

Definition satisfied.

Answer 2

If a sequence is convergent it is bounded. You have ${f(n)\over n^4}\to 0$ as $n\to\infty.$ Hence the sequence is bounded, so $f(n) = O(n^4).$