# Big-Oh notation asymptotic proof with faulty logic, trying to find the fault

What is wrong with this proof? According to the problem the claim of the proof is correct, but its not a sufficient proof. I'm a bit stumped on this one as to why it's not a valid proof, it seems so to me. I need to figure out where the issue is, I don't need to actually solve the proof itself but the fact that I can't find the issue worries me that maybe I don't even know its an issue and do it in my own proofs. Any help is appreciated. Thank you

Let $$f(n) = n^3 +n$$. We want to prove that $$f(n) \in O(n^3)$$. By the definition of Big-Oh, $$f(n) \in O(n^3)$$ iff $$f(n) \leq c*n^3$$ for some $$c > 0$$ and all $$n\geq n_0$$. Using the definition of $$f(n)$$, $$n^3 + n \leq c*n^3$$. Let $$c=2$$ and $$n_0 = 1$$. By substituting in, we have $$n^3 + n \leq 2n^3$$. So, subtracting an $$n^3$$ from both sides, we get $$n\leq n^3$$. Dividing by n for both sides, we get $$1\leq n^2$$ which is true for all $$n\geq n_0$$. So, $$f(n) \in O(n^3)$$

• I don't see anything wrong with your proof. Commented Apr 19, 2020 at 0:33

Notice, for all $$n \ge 1$$, we have $$n \le n^3$$. Therefore, $$f(n) = n^3 + n \le n^3 + n^3 = 2n^3$$. In our definition for big-O, this means our constant is $$c=2$$ and $$n_0 = 1$$. Thus by the previous calculation, $$f \in \mathcal O(n^3)$$
Alternatively, using a different definition of big-O, my preference would be that $$f \in \mathcal O(g)$$ iff $$\limsup_{x \to a} |f(x)/g(x)|=1$$. Then an alternative proof is
$$\limsup_{n \to \infty} \left| \frac{n^3 + n}{n^3} \right| = \limsup_{n \to \infty} \frac{1 + n^{-2}}{1} = 1$$ giving $$n^3 + n \in \mathcal O (n^3)$$. The steps between the two limits is that $$n,n^3 \ge 0$$ for $$n \ge 0$$, allowing us to remove the absolute value, and then we just divide by $$n^3$$ on top and bottom and calculate the obvious limit.