2
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.