find the worst-case-CodePudding

for(i=0;i<N;i  ){
  sequence of statements 
 }
for(j=0;j<M;j  ){
  sequence of statements
 }

how would the complexity change if the second loop went to N instead of M?

CodePudding user response：

tl;dr: O(N).

Instead of O(N M) it would then be O(2 * N) which is the same complexity class as O(N).

Of course under the assumption that "sequence of statements" run in constant time.

CodePudding user response：

If the first loop runs N times and Second M times it would be o(N M) , and if the second loop runs N then it would be o(N N) or o(2N) which means o(N). (Independent loops run in constant time)