Introduction

A double loop is often summarized as O(n^2), but that shortcut is only valid for certain loop bounds. In practice, nested-loop complexity depends on how each loop scales with input and whether inner work changes by iteration. Accurate analysis requires writing the operation count as a sum and simplifying it.

Base Case: Full Grid Iteration

Classic example where both loops iterate n times.

1def full_grid(n):
2    count = 0
3    for i in range(n):
4        for j in range(n):
5            count += 1
6    return count

Operation count is n * n, so time complexity is O(n^2).

Triangular Nested Loops

If inner bound depends on outer index, complexity can change.

1def upper_triangle(n):
2    count = 0
3    for i in range(n):
4        for j in range(i, n):
5            count += 1
6    return count

Count is sum of (n - i) for i from zero to n - 1, which simplifies to about n^2 / 2. Asymptotically it is still O(n^2).

Non-Quadratic Nested Loops

Double loops are not always quadratic. Example where inner loop doubles index.

1def logarithmic_inner(n):
2    count = 0
3    for i in range(n):
4        j = 1
5        while j < n:
6            count += 1
7            j *= 2
8    return count

Inner loop is O(log n), outer is O(n), total is O(n log n).

Early Exit and Best-Case Behavior

Conditionals and breaks can reduce average or best-case complexity.

1def search_matrix(matrix, target):
2    for i in range(len(matrix)):
3        for j in range(len(matrix[i])):
4            if matrix[i][j] == target:
5                return True
6    return False

Worst-case is full scan, but best-case is constant when target is at first cell.

Include Inner Operation Cost

If inner body does expensive work, multiply that cost too.

1def nested_with_sort(n):
2    arr = list(range(n, 0, -1))
3    for i in range(n):
4        for j in range(n):
5            arr.sort()

Here body is not constant. Sorting cost dominates, making total much larger than simple n^2.

Always include operation complexity inside loops, not only loop counts.

Space Complexity Considerations

Nested loops affect time primarily, but space depends on allocations in body. A quadratic loop with constant temporary variables can still be O(1) extra space. If each iteration stores values in a growing structure, space can become O(n^2) as well.

Analyze time and space separately.

Practical Analysis Workflow

A useful process:

1. express loop iteration counts clearly
2. convert to summation if bounds depend on indices
3. multiply by inner operation cost
4. simplify to dominant asymptotic term
5. note best and worst case if early exits exist

This avoids oversimplified answers in code reviews and interviews.

Common Misconceptions

Common mistakes include:

• assuming every double loop is O(n^2)
• ignoring data-dependent break conditions
• ignoring non-constant inner operations
• confusing actual runtime constants with asymptotic class

Asymptotic analysis compares growth, not exact milliseconds for one input size.

Common Pitfalls

• Labeling nested loops quadratic without checking loop bounds.
• Forgetting that triangular loops are still asymptotically quadratic.
• Missing log n inner loops that change final complexity class.
• Ignoring costly function calls inside loop bodies.
• Mixing time and space complexity in one unsupported claim.

Summary

• Double loops are often but not always O(n^2).
• Analyze loop bounds and inner operation cost together.
• Use summations for index-dependent bounds.
• Account for early exits when discussing best-case complexity.
• Separate time complexity from space complexity in final analysis.

Interview Communication Tip

When discussing nested loops in interviews, state both the formula and the reasoning path briefly. Showing the summation step and then the simplified order demonstrates stronger understanding than quoting complexity labels without derivation.