# Complexity analysis of while loop with two conditions

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?

• Why wouldn't $\min(n, m)$ be alright? It fully and accurately reflects the number of times the loop body is executed. – Patrick87 Jan 7 '14 at 21:06
• @Patrick87 Thanks for your quick answer! I added a small extension to show why I am not so sure about min(). – marekszpak Jan 7 '14 at 22:06

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.