Analyzing Nested Loops
What you'll learn: How to count operations in nested loops and recognize when runtime grows quadratically with input size.
The Core Idea
When you nest one loop inside another, the inner loop runs completely for every iteration of the outer loop. This multiplicative relationship causes operations to pile up much faster than a single loop.
If the outer loop runs n times and the inner loop runs n times for each outer iteration, the total primitive operations become n × n = n². This is called quadratic growth.
Counting Operations in Nested Loops
Consider this pattern:
for i from 0 to n-1:
for j from 0 to n-1:
perform one operation
Let's trace through for n = 3:
- When
i = 0: inner loop runs 3 times - When
i = 1: inner loop runs 3 times - When
i = 2: inner loop runs 3 times - Total: 3 × 3 = 9 operations
For n = 10, you get 100 operations. For n = 100, you get 10,000 operations. The runtime explodes quickly!
Real-World Analogy
Think of checking every pair of students in a classroom for matching birthdays. For each student (outer loop), you compare them with every other student (inner loop). With 30 students, that's roughly 900 comparisons—not 30!
Why This Matters
Nested loops are common in problems involving 2D arrays, comparing pairs, or finding patterns across data. Recognizing quadratic growth helps you understand why some programs slow down dramatically as input grows.
Key Takeaway: Nested loops multiply their iteration counts together; when both loops depend on input size n, runtime grows as n², creating quadratic complexity that scales poorly for large inputs.