Nested Loops
Is this starting to make sense?
I didn't like it when we went all the way down to defining problem size as number of bits (why!!??!), but if we can keep things sensible, I think I might be able to cope.
-
Yes, we'll keep that part more sensible. But actually that was a really simple algorithm. Algorithms we care about are often more complicated.
-
Oh no, I was afraid you'd say that… I need a lie down.
-
Don't worry! It's all just counting and adding, right? As long as you can break the program down into simple parts, you're fine!
One situation where breaking things down is trickier is when loops are nested within each other.
Example 1
Consider this snippet:
Cow bessie; // 1
for (size_t i = 0; i < m; ++i) { // 2
bessie.moo(); // 3
for (size_t j = 0; j < m; ++j) { // 4
bessie.moo(); // 5
} // 6
bessie.moo(); // 7
} // 8
bessie.moo(); // 9
Let's let
- \( n = \)
min the program, and - \( \mathrm{C}_{\mathtt{moo}}(n) \) be the number of times
bessiemoo()s when \( n = \)m.
Looking at our code, we see
| Line(s) | |
|---|---|
| 1 | There are no moo()s on line 1. |
| 2 | No moo()s on line 2, either, but we have the start of a loop from lines 2 through 8, which is run \( n \) times. |
| 3 | For each iteration of this loop we have one moo() on line 3. |
| 4 | We then have an inner loop from lines 4 to 6, which, again, runs \( n \) times. |
| 5 | Line 5 has a moo() each time through the loop. |
We can characterize the number of moo()s in the inner loop as \( \sum^{n}_{i=1} 1 = n \). |
|
| 6 | The inner loop ends at line 6. |
| 7 | We have one moo() on line 7. |
| 8 | The outer loop ends on line 8. |
We can characterize the number of moo()s in the outer loop as |
|
| \[ \sum^{n}_{i=1} ( 1 + n + 1 ) \; = \; n ( 1 + n + 1 ) \; = \; n(n + 2) \; = \; n^2 + 2n .\] | |
| 9 | We have one last moo() on line 9. |
Thus we can say that the number of moo()s in this code is \( \mathrm{C}_{\mathtt{moo}}(n) = n^2 + 2n + 1 \), where \( n = \) m.
-
Here's an optional video that goes over this argument.
Example 2
Consider this very similar snippet (the difference is highlighted in yellow):
Cow bessie; // 1
for (size_t i = 0; i < m; ++i) { // 2
bessie.moo(); // 3
for (size_t j = 0; j < 5; ++j) { // 4
bessie.moo(); // 5
} // 6
bessie.moo(); // 7
} // 8
bessie.moo(); // 9
Let's let
- \( n = \)
min the program, and - \( \mathrm{C}_{\mathtt{moo}}(n) \) be the number of times
bessiemoo()s when \( n = \)m.
Back to our code.
| Line(s) | |
|---|---|
| 1 | There are no moo()s on line 1. |
| 2 | We have a loop from lines 2 through 8; running \( n \) times (m times). |
| 3 | Line 3 has a single moo(), which is called each time the loop runs. |
| 4 | An inner loop runs from lines 4 through 6. It runs five times. |
| 5 | Line 5 has a moo() that runs each time through the inner loop. |
We can characterize the number of moo()s in this loop as \( \sum^{5}_{i=1} 1 = 5 .\) |
|
| 6 | The inner loop ends. |
| 7 | One more moo() on line 7. |
| 8 | Our outer loop closes. |
| So we can characterize the number of moos in the outer loop as | |
| \[ \sum^{n}_{i=1} (1 + 5 + 1 ) = \sum^{n}_{i=1} 7 = 7n . \] | |
| 9 | Finally, there is one more moo() on line 9. |
Thus, the total number of moo()s in this code is \( \mathrm{C}_{\mathtt{moo}}(n) = 7n + 1 \), where \( n = \) m.
-
We can also go over the analysis in a video…
Example 3
Consider one more similar snippet (the difference is highlighted in yellow):
Cow bessie; // 1
for (size_t i = 1; i <= m; ++i) { // 2
bessie.moo(); // 3
for (size_t j = 0; j < i; ++j) { // 4
bessie.moo(); // 5
} // 6
bessie.moo(); // 7
} // 8
bessie.moo(); // 9
Big hint: There is a really important formula attributed to Carl Friedrich Gauss via a fun, apocryphal story. [It also makes an appearance in s2e11, “2πR”, of Person of Interest!]
You should commit it to memory! It says that, for any \( N \geq 1 \), \[ \sum^{N}_{i=1} i = \frac{N(N + 1)}{2}. \]
| Line(s) | |
|---|---|
| 1 | There is no moo() on line 1. |
| 2 | The start of a loop that goes around \( n \) times. |
| 3 | In each iteration of this outer loop we have one moo() on line 3. |
| 4 | An inner loop starts on line 4, running i times. |
| 5 | Line 5 has one moo(), which runs each time through the loop. |
| 6 | We exit the inner loop. |
We can characterize the number of moo()s in the inner loop as \( \sum^{i}_{j=1} 1 = i \) |
|
| 7 | There is one moo() on line 7. |
| 8 | The outer loop ends on line 8. |
So we can characterize the number of moo()s in the outer loop as |
|
| \( \sum^{n}_{i=1} ( 1 + i + 1 ) = \sum^{n}_{i=1} i + \sum^{n}_{i=1} 2 \). | |
| Applying Gauss' formula (or using Wolfram Alpha), we can simplify to \( \frac{ n( n + 1 ) }{ 2 } + 2n = 0.5n^2 + 2.5n .\) | |
| 9 | There is one moo() on line 9. |
So, all together, the number of moo()s is \( \mathrm{C}_{\mathtt{moo}}(n) = 0.5n^2 + 2.5n + 1 \), where \( n = \) m.
-
And here's a video:
-
The main takeaway here is that it's all about adding things together!
-
Complicated algorithms may look intimidating at first, but very often you can break them into simpler blocks that aren't so scary.
(When logged in, completion status appears here.)