0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ "consists of several different algorithms": how are these algorithms combined ? $\endgroup$
    – user16034
    Jul 12, 2022 at 20:35
  • $\begingroup$ "it does not make sense": what is it ? $\endgroup$
    – user16034
    Jul 12, 2022 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 12, 2022 at 21:52

1 Answer 1

2
$\begingroup$

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 $

Addition.

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – David
    Jul 13, 2022 at 21:10
  • $\begingroup$ I'm afraid we don't understand each other. Written by me is just proved by the formal definition of approximation. Maybe you can formulate your problem in a different way? $\endgroup$
    – zkutch
    Jul 13, 2022 at 21:43
  • $\begingroup$ Since what is written is correct, then silent down voters are welcome to express their criticism explicitly. $\endgroup$
    – zkutch
    Jul 14, 2022 at 7:03
  • $\begingroup$ I am just asking if you have any idea about how it can be proved. $\endgroup$
    – David
    Jul 14, 2022 at 15:12
  • $\begingroup$ Ok. I'll add proof in nearest time. $\endgroup$
    – zkutch
    Jul 14, 2022 at 16:03

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.