# Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?

Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $$O(\log N)$$. Is the time complexity of our algorithm is $$m*O(\log N)$$ or it is $$O(\log N)$$. which one? Based on what I understand as the complexity is an approximation, the complexity is $$O(\log N)$$ but it does not make sense.

what about when we have different combination of big-Os like $$O(N), O(N^2), O(N/2)$$? we should choose the worst one; $$O(N^2)$$.

• "consists of several different algorithms": how are these algorithms combined ? Jul 12, 2022 at 20:35
• "it does not make sense": what is it ? Jul 12, 2022 at 20:35
• Since $m$ is at most $10$ (and at least $1$), $m \cdot O(\log N)$ and $O(\log n)$ represent the same set of functions. Jul 12, 2022 at 21:52

We have property $$O(f)+O(f)=O(f)$$ which means, that you can add big-$$O$$ fixed amount times and still get same. It's like your program have several consecutive parts with one and same complexity. Then all program have that complexity.

As to second question, then you can try to prove following $$O(n^{k}) + O(n^{m}) = O(n^{m})$$ when $$m>k>0$$

Assume $$\varphi \in O(n^{k}) + O(n^{m})$$. This means, that $$\varphi = \varphi_{1} + \varphi_{2}$$, where $$\varphi_{1} \in O(n^{k})$$ and $$\varphi_{2} \in O(n^{m})$$, i.e. are true following sentences: $$\exists C_{1} > 0, \exists N_{1} \in \mathbb{N}, \forall n > N_{1},\ \varphi_{1} \leqslant C_{1} \cdot n^{k}$$ $$\exists C_{2} > 0, \exists N_{2} \in \mathbb{N}, \forall n > N_{2},\ \varphi_{2} \leqslant C_{2} \cdot n^{m}$$ So we can write $$\varphi = \varphi_{1} + \varphi_{2} \leqslant C_{1} \cdot n^{k} + C_{2} \cdot n^{m} = n^{m}\left( C_{1} \cdot n^{k-m} + C_{2} \right)$$ when $$n>\max(N_1,N_2)$$. Because $$n^{k-m} <1$$, then $$\varphi \leqslant C \cdot n^{m}$$, where $$C = C_{1}+C_{2}$$. So, we obtain $$O(n^{k}) + O(n^{m}) \subset O(n^{m})$$.
• so I missed the real concept behind "approximation" hiding in Big-O. How can I prove this as it is not true that $m>>k$. without this assumption, the formal definition of Big-O cannot be used to prove the desired relationship. Jul 13, 2022 at 21:10