10
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ $O(n)$ is a set of functions. Do you mean set product here? $\endgroup$
    – Inuyasha Yagami
    Commented Aug 30, 2021 at 20:52
  • $\begingroup$ @InuyashaYagami if I got your question correctly, then yes $\endgroup$
    – illuminato
    Commented Aug 30, 2021 at 22:42

2 Answers 2

Reset to default
20
$\begingroup$

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 $$

Improve this answer
$\endgroup$
15
  • 5
    $\begingroup$ 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) $? $\endgroup$
    – Inuyasha Yagami
    Commented Aug 30, 2021 at 21:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – zkutch
    Commented Aug 30, 2021 at 22:25
  • 8
    $\begingroup$ 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)\}$? $\endgroup$
    – Bakuriu
    Commented Aug 31, 2021 at 6:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – John Coleman
    Commented Aug 31, 2021 at 16:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – zkutch
    Commented Aug 31, 2021 at 17:02
12
$\begingroup$

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)$

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ For numbers, or functions of numbers, one can define $A\cdot B=\{a\cdot b\mid \forall a\in A,b\in B\}$ $\endgroup$
    – nir shahar
    Commented Aug 31, 2021 at 11:53
  • 1
    $\begingroup$ @nirshahar Sure. It's just not how I would read $O(f)*O(g)$ in a paper about algorithm complexity. $\endgroup$
    – Taemyr
    Commented Aug 31, 2021 at 12:09
  • $\begingroup$ Yea, I agree that the specifics of the definition aren't that important. Just the fact we know what it means :) $\endgroup$
    – nir shahar
    Commented Aug 31, 2021 at 12:12
  • $\begingroup$ 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? $\endgroup$
    – illuminato
    Commented Aug 31, 2021 at 19:26
  • 2
    $\begingroup$ @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. $\endgroup$
    – Taemyr
    Commented Aug 31, 2021 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.