Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$.
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}) $.
