How to prove order of equation using Big-Oh notation?

109 Views Asked by At

How can I prove this order equation using Big-Oh notation? $$O(3n^3+2n^2+5) = n^3$$

2

There are 2 best solutions below

1
On BEST ANSWER

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.

0
On

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.