0
$\begingroup$

First case: I was stumble upon a two step sequential algorithm where the big O complexity of each step is $O(N^9)$.

Second case: Also if the algorithm have three steps where the complexity of step 1 is $O(N^2)$, the complexity of step 2 is $O(N^3)$ and the complexity of step 3 is $O(N^9)$

What would be the complexity of the first case and second case ?

$\endgroup$

1 Answer 1

1
$\begingroup$

In the first case, we have $O(n^9)+O(n^9)$ and according to it's summation properties we have $O(n^9)+O(n^9)=O(2n^9)=O(n^9)$.

For the second case, both $n^2$ and $n^3$ are smaller than $n^9$, so we have $O(n^2)+O(n^3)+O(n^9)=O(n^2+n^3+n^9)<O(n^9+n^9+n^9)=O(3n^9)=O(n^9)$

In the general case, if we have time complexities $t_1,t_2,...,t_k$, then $O(t_1)+...+O(t_k)=O(max\{t_1,...,t_k\})$

$\endgroup$
3
  • $\begingroup$ Thank you very much ! in the first case, if I can reduce the complexity of the second step to O(N^2) is it worth doing that since the complexity would be O(N^9) anyway ? $\endgroup$ Jun 22, 2020 at 13:17
  • $\begingroup$ In terms of complexity analysis its no different. In terms of actual running time - it will be an improvement, and the speedup will depend on the constants behind the $O(n^9)$ and the $O(n^2)$. $\endgroup$
    – nir shahar
    Jun 22, 2020 at 17:00
  • $\begingroup$ If you have changed a $0.00001n^9$ to a $999999999n^2$ then obviously thats not really an improvement $\endgroup$
    – nir shahar
    Jun 22, 2020 at 17:01

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.