Nested Loops and Big-O

Section 25.7 Nested Loops and Big-O

Subsection 25.7.1 Analyzing Nested Loops

What should the Big-O be for this nested loop?

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    cout << "*";
  }
  cout << endl;
}

Using the techniques from the previous section, we can identify that the inner loop runs \(n\) times. We also can tell that the outer loop runs \(n\) times. What do we do with those two \(n\)s?

🔗

It is important to recognize that the inner loop runs completely each time through the outer loop. If we run that code withn is 5, we print 25 stars (5 lines with 5 stars each).

🔗

*****
*****
*****
*****
*****

For each of the \(n\) iterations of the outer loop, we run the inner loop, which itself runs \(n\) times. This means that the code inside the inner loop (printing a single star here) runs a total of \(n \cdot n = n^2\) times.

🔗

Insight 25.7.1.

When loops are nested, we have to multiply their iteration counts to find the total work done.

🔗

If we simplify the contents of the outer loop using Big-O notation, we get:

🔗

for (int i = 0; i < n; i++) {
  // O(n) work for j loop
  // O(1) to print newline
}

Now we multiply that work by the number of iterations of the outer loop. \(n \cdot (O(n) + O(1)) = n \cdot O(n) = O(n^2) + O(n)\text{.}\) The dominant term is \(O(n^2)\text{,}\) so the entire nested loop is called \(O(n^2)\text{.}\)

🔗

Note that we could get the same answer by using Big-O logic on the contents of the loop. Inside the loop we are doing \(O(n)\) work for the inner loop and \(O(1)\) work to print the newline. So the entire contents of the outer loop is \(O(n) + O(1)\text{.}\) But in Big-O notation we only care about the dominant term. Here, that is \(O(n)\text{.}\) Thus we could write:

🔗

for (int i = 0; i < n; i++) {
  // O(n) work for j loop and constant work
}

Now analyzing the outer loop is just \(n \cdot O(n) = O(n^2)\text{.}\)

🔗

Insight 25.7.2.

You can simplify as you go using Big-O rules to make analysis easier.

🔗

What would the work be for these loops?

🔗

for (int i = 0; i < n; i++) {
  for (int j = 0; j < 10; j++) {
    sum = sum + i + j;
  }
}

Start with the inner loop. The inner loop runs 10 times. Each time through the inner loop, it does a constant amount of work. So the inner loop is \(10 \cdot O(1) = O(1)\text{.}\)

🔗

for (int i = 0; i < n; i++) {
  O(1) work for j loop
}

Now analyze the outer loop. The outer loop runs \(n\) times. Each time through the outer loop, it does \(O(1)\) work. So the entire nested loop is \(n \cdot O(1) = O(n)\text{.}\) Because the inner loop iterates a constant number of times, it does not affect the overall Big-O complexity.

🔗

Let’s consider one more example:

🔗

int i = 1;
while(i < n) {
  for (int j = 0; j < n; j++) {
    sum = sum + i + j;
  }
  i = i * 2;
}

The inner loop runs \(n\) times and does \(O(1)\) work each time, so the inner loop is \(O(n)\text{.}\) That gives us:

🔗

int i = 1;
while(i < n) {
  // O(n) work for j loop
  i = i * 2;
}

Now we have to analyze the outer loop. The counter i starts at 1 and is doubled each time through the loop. So the values of i are:

1, 2, 4, 8, 16, ..., n

🔗

That is a classic pattern (multiplied or divided by the same amount at each step) for \(O(\log n)\text{.}\)

🔗

Thus the entire nested loop is \(O(\log n) \cdot (O(n) + O(1)) = O(n \log n) + O(\log n)\text{.}\) The dominant term is \(O(n \log n)\text{,}\) so the entire nested loop is \(O(n \log n)\text{.}\)

🔗

Again, we could have simplified the contents of the outer loop first. It does \(O(n) + O(1)\text{,}\) but that is really just \(O(n)\text{.}\)

🔗

int i = 1;
// O(log n) iterations
  // O(n) work for j loop and constant work

Now analyzing the outer loop is just \(O(\log n) \cdot O(n) = O(n \log n)\text{.}\)

🔗

Subsection 25.7.2 Dependent Inner Loops

What about nested loops where the inner loop’s number of iterations depends on the outer loop’s counter? As in this sample:

🔗

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= i; j++) {
    cout << "*";
  }
  cout << endl;
}

If the n is 5, the output would be:

🔗

*
**
***
****
*****

Here, the inner loop runs a different number of times depending on the value of i. When i is 1, the inner loop runs 1 time. When i is 2, the inner loop runs 2 times. When i is 3, the inner loop runs 3 times. And so on, up to n.

🔗

We can do a rough estimate by thinking of the average cost of the inner loop. It is clear that the outer loop is repeating \(n\) (5) times. What is the average number of times the inner loop repeats? The middle line represents the average case - it repeats about \(\frac{n}{2}\) times. If \(n\) were 100, the middle line would have about ~50 stars. It doesn’t matter if the exact number is \(\frac{n}{2}\) or \(\frac{n + 1}{2}\) or any other similar formula. Those are all still dominated by \(n\) divided by a constant, which is \(O(n)\text{.}\)

🔗

So the inner loop is doing \(O(n)\) work on average. The outer loop runs \(n\) times, so the entire nested loop still does about \(n \cdot O(n) = O(n^2)\) work.

🔗

To more formally arrive at the same answer, we can figure out how to sum:

🔗

1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

By taking the first term and the last term and adding them we get \(1 + n = n + 1\text{.}\) Taking the second term and the second-to-last term we get \(2 + (n - 1) = n + 1\text{.}\) Then the third term and third-to-last also add to \(n + 1\text{.}\) Each pair of terms made working from the ends to the middle adds to \(n + 1\text{.}\)

🔗

How many such pairs are there? \(n\) items grouped into pairs will make \(\frac{n}{2}\) pairs. So the entire sum is about \(\frac{n}{2} \cdot (n + 1)\text{.}\)

\begin{equation*} \frac{n}{2} \cdot (n + 1) = \frac{n^2 + n}{2} = \frac{1}{2} n^2 + \frac{1}{2} n \end{equation*}

The dominant term is \(\frac{1}{2} n^2\text{,}\) which is \(O(n^2)\) in Big-O notation.

🔗

Insight 25.7.3.

In nested loops, when the outer loop does \(n\) iterations and the inner loops iteration count looks like: 1, 2, 3, ..., n-2, n-1, n then the total work done is \(O(n^2)\text{.}\)

🔗

This shortcut only applies to this situation where the inner loop’s iteration count increases linearly from 1 up to \(n\text{.}\) or if the inner loop iteration count starts from \(n\) and counts down to 1 as in something like:

🔗

for (int i = 1; i <= n; i++) {
  // print n - i + 1 stars... 1 fewer each iteration
  int numStars = n - i + 1;
  for (int j = 1; j <= numStars; j++)
    cout << "*";
  }
  cout << endl;
}

In more complex situations where the inner loop’s iteration count depends on the outer loop’s counter in a non-linear way, you may have to analyze the sum more carefully to find the exact Big-O. Fortunately, the linear increase/decrease case is the one we will usually bump into.

🔗

Subsection 25.7.3 Non-Nested Loops

Be careful when analyzing adjacent loops that are not nested. Consider this code:

🔗

for (int i = 0; i < n; i++) {
  cout << "*";
}
cout << endl;
for (int j = 0; j < n; j++) {
  cout << "#";
}
cout << endl;

How much work does it do?

🔗

The first loop runs \(n\) times, doing \(O(1)\) work each time, for a total of \(O(n)\text{.}\) The second loop also runs \(n\) times, doing \(O(1)\) work each time, for another \(O(n)\text{.}\) So we could simplify to:

🔗

// O(n) work for i loop
// O(1) to print newline
// O(n) work for j loop
// O(1) to print newline

That is \(O(n) + O(1) + O(n) + O(1) = 2 \cdot O(n) + 2 \cdot O(1)\) work overall which is just \(O(n)\text{.}\)

🔗

We only multiply Big-O terms when loops are nested, not when they are adjacent.

🔗

Using that knowledge, let’s evaluate:

🔗

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    cout << "*";
  }
  for (int k = 1; k < n; k *= 2) {
    cout << "#";
  }
  cout << endl;
}

The first inner loop is \(O(n)\text{.}\) The second inner loop is \(O(\log n)\) because the counter will be doubling at each step. So we can simplify to:

🔗

for (int i = 0; i < n; i++) {
  // O(n) work for j loop
  // O(log n) work for k loop
  // O(1) to print newline
}

If we simplify the work inside the outer loop, \(O(n) + O(\log n) + O(1)\text{,}\) the dominant term is \(O(n)\text{,}\) so we can call the entire chunk \(O(n)\text{.}\)

🔗

for (int i = 0; i < n; i++) {
  // O(n) for all the work
}

The outer loop has \(n\) iterations, so the entire code is \(n \cdot O(n) = O(n^2)\text{.}\)

🔗

Note 25.7.4.

We also could have multiplied \(n\) for the outer loop by all three parts of the inner loop:

\begin{equation*} O(n) \cdot (O(n) + O(\log n) + O(1) ) \end{equation*}

which produces

\begin{equation*} O(n^2) + O(n \log n) + O(n)\text{.} \end{equation*}

The dominant term is still \(O(n^2)\text{,}\) so we arrived at the same answer. But that is more work than simplifying as we go!

🔗

Checkpoint 25.7.1.

What is the Big-O classification of the following code fragment?

🔗

for (int i = 1; i <= 2*n; i++) {
  int curTotal = 0;
  for (int j = 1; j <= n; j++) {
    curTotal = curTotal + j;
  }
}

O(1)
The loops do not run constant number of times. They depend on n.
O(log n)
None of the loops involved repeat a logarithmic number of times.
O(n)
There is a nested loop, so the work is more than O(n).
O(n log n)
None of the loops involved repeat a logarithmic number of times.
O(n^2)

🔗

Checkpoint 25.7.2.

What is the Big-O classification of the following code fragment?

🔗

for (int i = 1; i <= n; i++) {
  int curTotal = 0;
  for (int j = 1; j <= n; j = j * 2) {
    curTotal = curTotal + j;
  }
}

for (int k = 1; k <= n; k++) {
  cout << k;
}

O(1)
The loops do not run constant number of times. They depend on n.
O(log n)
The inner loop of the nested loops runs in logn time. But it gets repeated.
O(n)
There is a nested loop, so the work is more than O(n).
O(n log n)
The inner loop of the nested loops runs in logn time. But it gets repeated n times. O(nlogn) for those loops dominates O(n) for the last loop.
O(n^2)
That would require an O(n) loop inside another O(n) loop. We do not have that.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next