# Can I multiply Big-O time complexities?

Can I multiply Big-O time complexities?

For example: $$O(n) \cdot O(n) = O(n^2)$$?

UPDATE:

The question came from my observation that different sources analyze their algorithms in different ways. For example, some use the following $$O(n \cdot n + n \cdot log (n) )$$ notation and some more like $$O(n) \cdot O(n) + O(n) \cdot O(log (n))$$ notation. I was wondering if it is equivalent notations.

• $O(n)$ is a set of functions. Do you mean set product here? Aug 30 at 20:52
• @InuyashaYagami if I got your question correctly, then yes Aug 30 at 22:42

Yes, you can and yes, it is.

Considering, for example, the non-negative case, we have a more general property: $$O(f)\cdot O(g) = O(f\cdot g )$$ Let's take $$\varphi \in O(f) \cdot O(g)$$. Then we have $$\varphi = \varphi_{1} \cdot \varphi_{2}$$ where $$\exists C_{1} > 0, \exists N_{1} \in \mathbb{N}, \forall n > N_{1},\ \varphi_{1} \leqslant C_{1} \cdot f$$ $$\exists C_{2} > 0, \exists N_{2} \in \mathbb{N},\ \forall n > N_{2},\ \varphi_{2} \leqslant C_{2} \cdot g$$ From above $$\varphi = \varphi_{1} \cdot \varphi_{2} \leqslant C_{1} \cdot f \cdot C_{2} \cdot g = C_{1} \cdot C_{2} \cdot f \cdot g$$ when $$n>N=max(N_{1},N_{2})$$.

Accordingly, we can also see that there is a second general property: $$O(f)+O(g) = O(f+ g )$$ The proof uses the same technique.

Definitions: $$O(f)\cdot O(g) = \left\lbrace a\cdot b \colon (a,b)\in O(f)\times O(g) \right\rbrace$$ $$O(f)+O(g) = \left\lbrace a + b \colon (a,b)\in O(f)\times O(g) \right\rbrace$$

• Hi zkutch. If I am understanding it correctly, you proved that if $\varphi \in O(f) \cdot O(g)$ then $\varphi \in O(f \cdot g)$. We might need to prove the vice-versa statement also, i.e., if $\varphi \in O(f \cdot g)$ then $\varphi \in O(f) \cdot O(g)$? Aug 30 at 21:50
• Yes, @Inuyasha Yagami. You are correct and I am very glad, that at last meet correctly seen situation, though many well known resources counts enough so called "one-way" direction. Of course, imo, equality of sets needs reverse inclusion, but let me suggest firstly wait OP reaction on brought. Proof of reverse direction is slightly more tricky, but also interesting. Aug 30 at 22:25
• What's the definition of $O(f) \cdot O(g)$ that you are using? Is $O(f) \cdot O(g) = \{ f_i \cdot g_j \mid f_i \in O(f), g_j \in O(g)\}$? Aug 31 at 6:49
• If you think that proofs of equality of sets requires two inclusions, why settle for just one? The fact that OP is satisfied with half a proof doesn't mean that you need to be. Aug 31 at 16:37
• Because it is answer to question @John Coleman. Please note that the questioner does not ask for proof, the question is about the validity of using certain notations. I showed a technique that allows you to restore the missing 3/4 parts yourself. Also, let me say that sometimes adding a lot of details complicates the answer, making it cumbersome and difficult to understand. If you, or anyone else, are interested in the proofs, then just write about it, perhaps better in a new question, so as not to clutter up this one, and I will answer with pleasure. Aug 31 at 17:02

It's an abuse of notation.

$$O(n)$$ is a set of functions.

So $$O(n)*O(n)$$ is not really defined. $$O(n)\times O(n)$$ is defined, but it is defined as cartesian products of the set of functions in $$O(n)$$ by itself. This is probably not what you are after.

Within the context of algorithm analysis most would interpret $$O(f)*O(g)$$ to mean that we do some operation a number of time bounded by $$f$$, and each operation takes relevant resource (e.g. time or space) bounded by $$g$$. By that interpretation $$O(f)*O(g)\subset O(f*g)$$

• For numbers, or functions of numbers, one can define $A\cdot B=\{a\cdot b\mid \forall a\in A,b\in B\}$ Aug 31 at 11:53
• @nirshahar Sure. It's just not how I would read $O(f)*O(g)$ in a paper about algorithm complexity. Aug 31 at 12:09
• Yea, I agree that the specifics of the definition aren't that important. Just the fact we know what it means :) Aug 31 at 12:12
• Thanks for the answer. So would you recommend using e.g. $O(n \cdot n + n \cdot log (n) )$ notation instead of $O(n) \cdot O(n) + O(n) \cdot O(log (n))$ when analyzing time complexities? Aug 31 at 19:26
• @illuminato I would recommend $O(n^2)$ as the conclusion, and both your notations only as intermediary steps. But those intermediary steps should be accompanied with enough text that it is clear what you mean. Aug 31 at 19:51