How to show properly $ 10n^4 + 3n^3 -n \in O(n^4)$?

Question

Given: $$ 10n^4 + 3n^3 -n \in O(n^4)$$

So i do understand Big O and what it does. I am however not quite if my approach for the solution is correct, so anyone who could help me out or show me an alternative approach if mine is not correct would be awesome. My solution:

$$ \lim_{x\to\infty} \frac {f(x)}{n^4} \ = 10 => f(n) = \Theta(n^4)$$

so $$ 10n^4 + 3n^3 -n \in O(n^4)$$

is not true. Plotting both functions seem to show exactly what i found out:

Is that however correct?

Answer 1

By definition $10n^4+3n^3−n\in O(n^4)$ if and only if there exist $n_0$ and $M$ such that $$|10n^4+3n^3−n|\leq M n^4 \quad \forall n\geq n_0.$$ Using triangular inequality and the fact that $n^4$ is larger or equal than $n^3$ and $n$ (if $n\geq 1$) yields $$|10n^4+3n^3−n|\leq |10n^4|+|3n^3+|-n|=10n^4+3n^3+n\leq 10n^4+3n^4+n^4 = 14 n^4 \quad \forall n\geq 1$$ the definition is fulfilled with $M=14$ and $n_0=1$ and thus $10n^4+3n^3−n\in O(n^4)$.

Equivalently, since $\lim_{n\to\infty}\frac{10n^4+3n^3−n}{n^4}=10 $, then $10n^4+3n^3−n\in O(n^4)$.

Answer 2

You seem to be confused about what the big-O notation means. Since $$\lim_{n\to\infty} \frac {f(n)}{n^4} = 10,$$ we know that for sufficiently large $n$, $$\frac {f(n)}{n^4}<15\implies f(n)<15n^4\implies f(n)=O(n^4)$$

Since $$\lim_{n\to\infty}\frac {n^4}{f(n)}=1,$$ it is also true that $$n(n)=\Theta(n^4),$$ but this in no way invalidates the statement that $f(n)=O(n^4)$. It is, in fact, a stronger statement.

I don't understand how you believe the graph contradicts this statement, but it cannot, since the statement is true.

EDIT

Any number greater than $10$ can be used in place of $15$. $\lim_{n\to\infty} \frac {f(n)}{n^4} = 10$ means that $\forall \varepsilon > 0\ \exists N$ such that $n>N\implies \left\lvert \frac {f(n)}{n^4}-10\right\rvert <\varepsilon$. If we take $\varepsilon =5$, we get $5<\frac{f(n)}{n^4}<15$.

Answer 3

As Yves mentionned, $f(n) \in \Theta(n^4)$ implies that $f(n) \in O(n^4)$.

Big O notation matters only as $n \rightarrow + \infty$, that is why you are computing the limit of the function over $n^4$ only there.

You do not care that $f$ goes below $n^4$ for small values, what big O says is "for sufficiently large values of $n$, $f$ is lower than some $k n^4$ for some fixed $k$". You can check that $f$ is indeed smaller than $11n^4$ in the limit if you want to convince yourself.