Show that $n^3-5n+1=O(n^3)$. I did the following: Using the definition of big-Oh, we need to show that there exist $n_0$ and $C$ such that $n^3-5n+1 \leq Cn^3$ is valid for some constant $C > 0$ and for all $n > n_0$. First, choose $n_0=1$. Then $1^3-5 \cdot 1+1=C\cdot 1^3$=> $C=-3$. Since by definition of big-Oh, $C$ should be greater than $0$. $C= -3$ should not work. How can I prove this order of complexity?
Asked
Active
Viewed 394 times
2 Answers
2
Hint: The condition is really $$\bigl|n^3-5n+1\bigr| \leq Cn^3$$ so you can use the triangle inequality.
Another approach: a polynomial is asymptotically equivalent to its leading term, so $n^3-5n+1\sim_\infty n^3$, which is stronger than being $O\bigl(n^3\bigr)$.
Bernard
- 175,478
1
There might be some ambiguity with the definition that you are working with, but at least for me I am used to $f(x)=O(g(x))$ if there is $x_0\in\mathbb{R}$ and $C\geq 0$ such that $x\geq x_0$ implies $|f(x)|\leq Cg(x)$ (notice the absolute values). Then in your case, choose $n_0=5$ and $C=1$. We have for $n\geq n_0$
$$0<n(n^2-5)=n^3-5n<n^3-5n+1<n^3$$
Then
$$|n^3-5n+1|\leq 1\cdot n^3$$
implies $n^3-5n+1=O(n^3)$.
QC_QAOA
- 11,796
-
How can I also prove this: If f1 is O(f2) and f2 is O(g), then f1 is O(g). – Buddy Nov 26 '20 at 01:37
-
-