How can I prove this order equation using Big-Oh notation? $$O(3n^3+2n^2+5) = n^3$$
Asked
Active
Viewed 106 times
-1
-
It is not a linear equation. What is the rank of this equation. – Bernard Jun 06 '15 at 12:04
-
It is also not an equation. There needs to be an equals sign for something to be an equation. – Thomas Andrews Jun 06 '15 at 12:06
-
the question is edited; I am asking the prove of order. fyi @Bernard and Thomas Andrews – talha06 Jun 06 '15 at 12:21
-
1$\lim_{n\to\infty} (3n^3+2n^2+5)/n^3 = 3 \ne 0$ – Michael Galuza Jun 06 '15 at 12:23
2 Answers
2
By the definition of the big-O, the equation reads as $"$there are constants $N$ and $C$ such that
$$\forall n\ge N:n^3\le C(3n^3+2n^2+5)."$$
Clearly, $N=C=1$ make it true.
2
The equation $n^{3} = O(3n^{3} + 2n^{2} + 5)$ (with "as $n \to \infty$" when speaking of asymptotics) means that there is some $M > 0$ such that $$n^{3} \leq M(3n^{3} + 2n^{2} + 5)$$ for large $n$. But, since $$\frac{n^{3}}{3n^{3} + 2n^{2} + 5} = \frac{1}{3 + \dfrac{2}{n} + \dfrac{5}{n^{3}}} < 1$$ for all $n \geq 1,$ the equation under consideration holds.
Yes
- 20,719
-
Please also note that the equal sign linking the big O is simply a shorthand. – Yes Jun 06 '15 at 13:10