Introduction

Time complexity measures how an algorithm's running time grows as the input size increases. Nested loops -- loops placed inside other loops -- are the most common source of higher-order time complexities. Understanding how to analyze them is a foundational skill in computer science, because a small change in loop structure can move you from an efficient algorithm to one that becomes unusable on large inputs.

O(n^2) -- Independent Nested Loops

The classic case is two loops that each run from 0 to n, where the inner loop is independent of the outer loop variable:

1def print_pairs(arr):
2    n = len(arr)
3    for i in range(n):        # runs n times
4        for j in range(n):    # runs n times for each i
5            print(arr[i], arr[j])

The outer loop executes n iterations. For each of those, the inner loop also executes n iterations. The total number of print calls is n * n = n^2.

Big-O derivation: T(n) = n * n = n^2, so the time complexity is O(n^2).

This pattern appears in brute-force searching (checking every pair), simple sorting algorithms like Bubble Sort and Selection Sort, and adjacency-matrix graph traversals.

O(n * m) -- Two Different Input Sizes

When the outer loop depends on one input and the inner loop depends on a different input, the complexity involves both:

1def compare_lists(list_a, list_b):
2    for a in list_a:           # runs n times (n = len(list_a))
3        for b in list_b:       # runs m times (m = len(list_b))
4            if a == b:
5                print("Match:", a)

Big-O derivation: T(n, m) = n * m, so the time complexity is O(n * m). This is not O(n^2) unless you know that n and m are always equal. When analyzing complexity, treat different inputs as separate variables.

O(n^2 / 2) -- Dependent Inner Loop

Sometimes the inner loop's range depends on the outer loop variable. This is common when you want to avoid duplicate pair comparisons:

1def unique_pairs(arr):
2    n = len(arr)
3    for i in range(n):
4        for j in range(i + 1, n):   # starts at i+1, not 0
5            print(arr[i], arr[j])

When i = 0, the inner loop runs n - 1 times. When i = 1, it runs n - 2 times. The total is:

(n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2

Big-O derivation: T(n) = n(n-1)/2 = (n^2 - n)/2. Dropping the constant factor and lower-order term, this is still O(n^2). The constant 1/2 disappears in Big-O notation because we care about growth rate, not exact count. However, in practice this runs about twice as fast as the fully independent version.

O(n log n) -- Logarithmic Inner Loop

When the inner loop variable doubles or halves on each iteration instead of incrementing by 1, it produces a logarithmic number of steps:

1def log_inner(n):
2    for i in range(n):         # runs n times
3        j = 1
4        while j < n:           # runs log2(n) times
5            print(i, j)
6            j *= 2             # doubles each iteration

The inner while loop starts at 1 and doubles until it reaches n. The number of doublings is log2(n). Since the outer loop runs n times, the total is n * log2(n).

Big-O derivation: T(n) = n * log(n), so the time complexity is O(n log n). This is the same complexity class as efficient sorting algorithms like Merge Sort and Heap Sort.

How to Analyze Any Nested Loop

Follow these steps for any nested loop structure:

1. Identify each loop's iteration count as a function of n (or m, or the outer loop variable).
2. Multiply the counts for independent loops. If the outer runs a times and the inner runs b times, total work is a * b.
3. Sum the counts for dependent loops. Write out the summation and compute the closed form.
4. Drop constants and lower-order terms to get the Big-O class.

The same principle extends to deeper nesting. Three independent loops each running n times give O(n^3), four give O(n^4), and so on.

Common Pitfalls

• Assuming all nested loops are O(n^2): If the inner loop runs a constant number of times (say, always 5), the overall complexity is O(5n) = O(n), not O(n^2). Always check whether the inner loop depends on n.
• Forgetting that O(n * m) is not O(n^2): When two loops iterate over different-sized inputs, use two variables. Collapsing them into n^2 leads to incorrect analysis.
• Ignoring logarithmic inner loops: When the loop variable doubles or halves each iteration, the inner loop runs in O(log n), not O(n). The combined complexity is O(n log n), which is dramatically better than O(n^2) for large inputs.
• Dropping the summation step for dependent loops: When the inner loop range depends on the outer variable, you must compute the summation (for example, 1 + 2 + ... + n = n(n+1)/2) before simplifying. Skipping this step leads to wrong answers.
• Confusing Big-O with exact count: O(n^2) means the growth rate is quadratic. Two algorithms can both be O(n^2) while one is consistently twice as fast. Big-O tells you the shape of the curve, not the exact running time.

Summary

• Two independent nested loops each running n times give O(n^2).
• Loops over two different inputs of size n and m give O(n * m) -- keep the variables separate.
• Dependent inner loops (starting at i instead of 0) still produce O(n^2) because the sum 1 + 2 + ... + n equals n(n-1)/2.
• An inner loop that doubles or halves its variable produces O(n log n) when paired with an O(n) outer loop.
• Always compute the summation for dependent loops and drop constants and lower-order terms to find the Big-O class.