Nested Loops Multiply

Here is a method that checks whether two arrays share a common element:

public boolean hasCommonElement(int[] a, int[] b) {
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      if (a[i] == b[j]) {
        return true;
      }
    }
  }

  return false;
}

Again take both arrays to have length $n$. How much work does this do, and what is its Big-Oh?

The code looks a lot like the previous example.

The loops are nested. For each of the $n$ elements of a, the inner loop runs over all $n$ elements of b. So every pair (a[i], b[j]) gets compared. It helps to draw those pairs as a grid. The outer index i picks a row, and for that row the inner loop runs over every column j. Each cell of the grid is one comparison.

      j=0  j=1  j=2  j=3
i=0   ░    ░    ░    ░
i=1   ░    ░    █    ·
i=2   ·    ·    ·    ·
i=3   ·    ·    ·    ·

Here we are partway through. A · is a comparison we have not made yet, a ░ is one we have already made, and the █ is the comparison happening right now.

In the worst case the two arrays share no element at all. No comparison ever finds a match, and the inner loop runs over every column of every row.

      j=0  j=1  j=2  j=3
i=0   ░    ░    ░    ░
i=1   ░    ░    ░    ░
i=2   ░    ░    ░    ░
i=3   ░    ░    ░    ░

That means the inner comparison happens once for every cell of the grid. The grid has $n$ rows and $n$ columns, so that is $n\times n=n^2$ comparisons, each a constant amount of work.

That is $O(n^2)$.

Now compare this with the previous section. There the loops were sequential, so their work added, $n+n$. Here one loop is inside the other, so their work multiplies, $n\times n$. Sequential loops add and nested loops multiply.

The equal array sizes are again just to keep the analysis simple. With sizes $m$ and $k$, the work is $O(m\times k)$.