# 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? Commented Aug 30, 2021 at 20:52
• @InuyashaYagami if I got your question correctly, then yes Commented Aug 30, 2021 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)$? Commented Aug 30, 2021 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. Commented Aug 30, 2021 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)\}$? Commented Aug 31, 2021 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. Commented Aug 31, 2021 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. Commented Aug 31, 2021 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\}$ Commented Aug 31, 2021 at 11:53
• @nirshahar Sure. It's just not how I would read $O(f)*O(g)$ in a paper about algorithm complexity. Commented Aug 31, 2021 at 12:09
• Yea, I agree that the specifics of the definition aren't that important. Just the fact we know what it means :) Commented Aug 31, 2021 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? Commented Aug 31, 2021 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. Commented Aug 31, 2021 at 19:51