How would I begin to check if the function is $O(x^4)$?

Question

Use the definition

$f(x) $ is in $O(g(n))$ if, for some constants $c$ and $n_0, f(n) ≤ g(x) $ for all $n > n_0$

To show that

$ x^4 + 9x^3 + 4x + 7$ is $O(x^4)$

I know I need to find $c$ and $n_0$ and I thought $c$ needed to be $2$. The problem is there is no positive $n_0$ for which this is true.

Please read the description of the tag "discrete-mathematics". It tells you what to do when the question is not programming-related! ;) — , Oct 06 '19 at 07:52
I'm voting to close this question as off-topic because it's a pure math question. — , Oct 08 '19 at 09:52
Also note that c doesn't need to be 2. 10 x^4 - 10 x^3 is also O(x^4). If you can't find a small enough n0 you typically just increase the c until you do (do verify that it holds for all ns though!) — Jochem Kuijpers, Oct 05 '19 at 21:44

score 0 · Answer 1 · answered Oct 12 '19 at 17:40

For $n \ge 1$, all of $n^0, n^1, n^2, n^3$ are less than $n^4$. So $$n^4 + 9n^3 + 4n + 7 \le n^4 + 9n^4 + 4n^4 + 7n^4 = 21n^4.$$ This is the easy way to look at the problem.

It is also true, that if you have a polynomial $f(x) = a_4x^4 + a_3x^3 + x_2x^2 + a_1x^2 + a_0$ then $$f(n) \le (a_4 + \varepsilon) n^4$$

for any $\varepsilon > 0$ and all $n \ge n_0$ where $n_0$ will depend on $\varepsilon$. In your question, since $a_4 = 1$, you get $f(n) \le 2n^4$ ($\varepsilon = 1$) for $n \ge 10$ (see https://www.desmos.com/calculator/rdxgl82bb2).

To show this, you need to show that $$ a_3n^3 + x_2n^2 + a_1n^2 + a_0 \le \varepsilon n^4$$ for $n$ sufficiently large. The easiest way to do this is to consider the limit

$$ \lim_{x \to \infty} \frac{a_3x^3 + x_2x^2 + a_1x^2 + a_0}{x^4}. $$

Some questions you should think about:

Why does $c$ need to be greater than $a_4$?
What happens if some of the coefficients are negative?
Is there a way to compute an $n_0$ given $\varepsilon$? Either the smallest $n_0$ that works or any $n_0$ that works.

How would I begin to check if the function is $O(x^4)$?

1 Answers1