Complexity analysis of while loop with two conditions

Problem Detail: 

I am curious how to do a line by line analysis of this piece of code using the "Big O" notation.

i = 0; j = 0;  while ( ( i < n ) && ( j < m ) ) {       //do something       i++;       j++; } 

How I should represent number of iterations for the loop? Is good if I will do some assumptions or I should write min(n, m)?

Small extension after @Patrick87's comment to show why I am not sure that min() is a general solution:

i = 0; j = 0;  while ( ( i < n ) && ( j < m ) ) {       //do something       i++;       j++; } if ( i < n ) {       while ( ( i < n ) )       {          //do something          i++;       } } else {       while ( ( j < m ) )       {          //do something          j++;       } } 

How right now we can connect a number of iterations of the first loop and second one if we don't know which condition broke the condition of the first loop?

Asked By : marekszpak

Answered By : Logan Mayfield

As Patrick87 pointed out. The first loop is $\min(m,n)$. As for your extended question, it's unclear if you want best, worst, or average case. We typically look at worst case. Either way, you seem to be focused on a single execution when you really need consider all possible $i$ and $j$ values. So, let's do that:

1. $m = n$.

In this case the additional conditional does no work, so the total run time is still $O(\min(m,n))$.

1. $m < n$.

When this is true, then the first loop terminates due to $j$. The conditional will then carry out the first case $i < n$ and terminate after $O(n-m)$ iterations. The total number of operations is then $O(n-m+m)= O(n)$ operations.

1. $m > n$.

This case is equivalent to the second case but the result is $O(m)$.

Now observe that cases 1,2, & 3 are all equivalent to $O(\max(m,n))$. This is the running time for your code.

So back to your "how to" question. You need to do a good, thorough case analysis for multi-conditional loops just like you need to do with conditionals. Then analyze the running time of each case and, assuming your doing worst case analysis, take the largest running time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19564