Big O notation Problems

Question

I have read a lot of articles on Big O notation but never found a problem like this and I have no idea how to solve it.

$$3 \cdot O(n^3) = O(3 + n^3)$$

Answer 1

I will talk first about the RHS: the term with the highest degree (in this case $n^3$) dominates the other terms with a smaller degree (in this case $3\equiv 3\cdot n^0$) when $n$ becomes large (think of what happens when $n\in(0, 1)$ and compare with what happens when $n \ge 1$). Notice that $\mathcal O\left(3 + n^3\right)\equiv\mathcal O\left(3\cdot n^0 + n^3\right)\equiv\mathcal O\left(n^0 + n^3\right)$ [why? refer to this and this]. Now, since $n^3$ has a higher degree than $n^0$, the former dominates the latter for sufficiently large values of $n$. Therefore, $\mathcal O\left(n^0 + n^3\right)\equiv\mathcal O\left(n^3\right)$.

Now, for the LHS, you can think of $3\cdot\mathcal O\left(n^3\right)$ as $\mathcal O\left(n^3\right) + \mathcal O\left(n^3\right) + \mathcal O\left(n^3\right)$. This is the same as $\mathcal O\left(n^3 + n^3 + n^3\right)$ [why? refer to this] which in turn is equivalent to $\mathcal O\left(3\cdot n^3\right)$. And we already know from the discussion above that this expression is fundamentally equal to $\mathcal O\left(n^3\right)$.

Answer 2

I think the satatement is pretty intutive since both the LHS and RHS are dominated by the $n^{3}$, so both LHS and RHS are $O(n^{3})$. Anyhow, I tried proving it this way...

Starting with the following definition of Big-O: $f(x)=O(g(x))$ if there exists a positive real number $K$ and a real number $x_{0}$ such that $$\bigl|f(x)\bigr|\leq K \cdot g(x)$$ $\forall x>x_{0}$.

Now let $f_{1}(n)=3\cdot O(n^{3})$ and $f_{2}(n)=O(3+n^{3})$. By definition this means that $$f_{1}(n)\leq 3\cdot K_{1}\cdot n^{3}\leq K_{1}^{'}\cdot n^{3}$$ $\forall n> n_{0}$. So $\boxed{f_{1}(n)=3\cdot O(n^{3})=O(n^{3})}$ and $$f_{2}(n)\leq K_{2}\cdot (3+n^{3})=K_{2}\cdot 3+K_{2}\cdot n^{3}\leq K \cdot n^{3}$$ $\forall n>n_{0}$. That is $\boxed{f_{2}(n)=O(3+n^{3})=O(n^{3})}$. In conclusion we have that $f_{1}(n)=O(n^{3})=f_{2}(n)$, meaning in particular that $$3\cdot O(n^{3})=O(n^{3})=O(3+n^{3}).$$