Course contentsShow
← Computer Science
Lesson 275 of 2,8727. Introduction to Complexity AnalysisFree lesson

Analyzing Nested Loops

Computing runtime for nested loop structures and recognizing quadratic growth patterns.

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.