How to prove that $O(n) \cdot O(n^2) = O(n^3)$?

Question

Would the solution be something like

let $fn \in O(n)$ so $ fn \le c1 \cdot n$ and $ gn \in O(n^2) $ so $ gn \le c2 \cdot n^2$ where $c1,c2$ constants

so $ fn*gn \le C \cdot n^3$ so $ fn*gn \in O(n^3)$ so $O(n) \cdot O(n^2) = O(n^3)$

Answer 1

Yes, you are exactly right.

Maybe even $$fn \cdot gn \leq c_1 n \cdot c_2 n^2 \leq C n^3 = O(n^3)$$ for more clarity.

---

note: When speaking of complexity classes, the equality sign is often used insted of $\in$ which would be formally more correct.

If you also need to prove $O(n^3) \subseteq O(n) \cdot O(n^2)$, the argument would go the same similarly (see comments below for details).

Answer 2

Recall that

$$O(n)=\omega_1(n)\cdot n \quad \limsup_{n\to \infty} |\omega_1 (n)|=c_1\in \mathbb{R}$$

$$O(n^2)=\omega_2(n)\cdot n^2 \quad \limsup_{n\to \infty} |\omega_2 (n)|=c_2\in \mathbb{R}$$

therefore

$$O(n) \cdot O(n^2)=\omega_1 (n)\cdot\omega_2(n)\cdot n^3=\omega_3(n)\cdot n_3=O(n^3)$$

indeed

$$\limsup\left|\omega_3(n)\right|\le\limsup\left|\omega_1 (n)\right|\cdot \limsup\left|\omega_2(n)\right|=c_1\cdot c_2=c_3\in \mathbb{R}$$

Answer 3

First, there seems to be some confusion about what you are asked to prove: what does $$\tag{1} O(n) \cdot O(n^2) = O(n^3)$$ mean, exactly?

The interpretation I'm familiar with, in the words of Cormen et al., is the following:

In some cases, asymptotic notation appears on the left-hand side of an equation, as in $$2n^2 + \Theta(n) = \Theta(n^2)\text{ .}$$ We interpret such equations using the following rule: No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.

(Cormen et al., "Introduction to Algorithms", 3rd Ed., section 3.1, page 50.)

Note how this makes the $\;=\;$ operator asymmetrical. Note also that this makes $\;f(n) = O(g(n))\;$ mean $\;f \in O(g(n))\;$.

$% \require{begingroup} \begingroup \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} %$This interpretation says that $\Ref{1}$ is equivalent to: $$ \begin{align}& \langle \forall f,g :: f \in O(n) \;\land\; g \in O(n^2) \;\then\; \\&\phantom{\langle \forall f,g ::\;} \langle \exists h :: h \in O(n^3) \;\land\; \langle \forall n :: f(n) \cdot g(n) = h(n) \rangle \rangle \rangle \end{align} $$ or simplified: for all $\;f,g\;$, $$ \tag{1a} f(n) = O(n) \;\land\; g(n) = O(n^2) \;\then\; f(n) \cdot g(n) = O(n^3) $$

---

Now, how would we prove $\Ref{1a}$? You have the correct idea essentially, and let's try to write this down as cleanly as possible, using the definition that you seem to be using, which is $$ \tag{2} f(n) = O(g(n)) \;\equiv\; \langle \exists c : c > 0 : \langle \forall_{\text{large enough }} n :: f(n) \le c \cdot g(n) \rangle \rangle $$

It seems simplest to start with $\;f(n) \cdot g(n)\;$, and rewrite that using the assumptions in the left hand side of $\Ref{1a}$:

$$\calc f(n) \cdot g(n) \op{\le_{\forall_{\text{large enough }} n}}\hints{using the LHS of $\Ref{1a}$ and definition $\Ref{2}$ twice,}\hint{choose $\;c_1,c_2 > 0\;$} c_1 \cdot n \cdot c_2 \cdot n^2 \op=\hint{arithmetic} (c_1 \cdot c_2) \cdot n^3 \op=\hint{using definition $\Ref{2}$ with $\;c := c_1 \cdot c_2\;$} O(n^3) \endcalc$$

By transitivity of the three steps, this proves $\Ref{1a}$.

---

A side note: The above proof of course doesn't just work for $\;n\;$ and $\;n^2\;$, but for any functions $\;F(n),G(n)\;$: in the same way we can prove the more general $$\tag{3} O(F(n)) \cdot O(G(n)) = O(F(n) \cdot G(n))$$

---

Finally, what about proving the other direction? I would write this as $$\tag{4} O(n^3) = O(n) \cdot O(n^2)$$ and Cormen et al. says this means we need to prove \begin{align} \tag{4a} &\langle \forall f :: f \in O(n^3) \;\then\; \\&\phantom{\langle \forall f :: \;} \langle \exists g,h :: g \in O(n) \land h \in O(n^2) \land \\&\phantom{\langle \forall f :: \langle \exists g,h :: \;} \langle \forall n :: f(n) = g(n) \cdot h(n) \rangle \rangle \rangle \end{align}

So given an $\;f \in O(n^3)\;$, there seem to be two simple choices, one of which is $\;g(n) = f(n) / n^2\;$, and $\;h(n) = n^2\;$. All that is then left to prove is $\;f(n)/n^2 = O(n)\;$ and $\;n^2 = O(n^2)\;$, which are easy exercises from definition $\Ref{2}$.

(Note that I'm assuming here that $\;n\;$ ranges over positive integers, to avoid technical manipulations to avoid division by zero.)

And again, of course this proof generalizes immediately to a proof of $$O(F(n) \cdot G(n)) = O(F(n)) \cdot O(G(n))$$

The only qualm I have with this proof is that it isn't really symmetrical in $\;g\;$ and $\;h\;$: we could have equally well have chosen $\;g(n) = n\;$ and $\;h(n) = f(n) / n\;$. I tried to find a more symmetrical choice for $\;g,h\;$, but don't see it yet.

$% \endgroup %$