Nested Loop Time Complexity: The O(n²) Rule and Its Exceptions

"O(n²)" is the reflex answer for nested loops. Confident, immediate, sometimes delivered before the code is even finished. And wrong often enough that interviewers write things down.

The real rule: total iterations equal the product of each loop's iteration count. The hard part is figuring out how many times each loop actually runs, which is not obvious when bounds depend on each other or when the inner body is secretly calling a sort.

Five patterns cover nearly everything you will see in interviews.

The Simple Case: Multiply the Bounds

A nested loop executes the inner body once for every combination of outer and inner index. Total executions: outer iterations times inner iterations per outer step.

for i in range(n):       # n times
    for j in range(n):   # n times each
        print(i, j)      # runs n × n = n² times total

Body is O(1), so total is O(n²). Add a third loop over n and you get n³. Add a fourth and you get n⁴. You're always multiplying. It gets interesting when the loops are not symmetric.

The Dependent Bound Is Still O(n²)

The most common interview variation:

for i in range(n):
    for j in range(i):  # runs 0, 1, 2, ..., n-1 times
        print(i, j)

The inner loop runs 0 times when i=0, 1 time when i=1, up to n-1 times when i=n-1. Sum them:

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

That's the triangular number formula. Expand it: n²/2 - n/2. Drop the constant and the lower-order term. You still get O(n²), not O(n²/2), not O(n log n).

This trips people up because the dependent inner loop looks cheaper than two full sweeps over n. It is cheaper by a constant factor of 2. Big-O doesn't care about constant factors. Not now, not ever.

Bubble sort, insertion sort, and any algorithm that compares each element to every earlier element all follow this pattern. Knowing the triangular sum lets you derive their complexity instead of memorizing it.

Algorithm complexity tier list meme: Computer Nerd's algorithm is O(1), A-Student's Algorithm is O(N), My Algorithm is O(N!)

Yes, O(n²) feels painful. Perspective helps.

Two Different Inputs: O(n × m)

When inputs have two independent sizes, name them both:

for row in range(rows):
    for col in range(cols):
        grid[row][col] = 0

This is O(rows × cols). Calling it O(n²) is wrong unless you explicitly define n as the total number of cells.

In grid problems, state the dimensions separately. An interviewer notices when you collapse a 1000×10 grid into "n²" as if it were 1000×1000. It isn't. The correct form is O(m × n). If they happen to be equal, O(n²) is fine with a clarifying note.

The same rule applies to string comparison (lengths m and n), two separate arrays, and graphs. For a graph with V vertices and E edges, most traversal algorithms are O(V + E), not O(V²), because edges determine the inner work, not the vertex count alone.

The One Nested Loop That Is Not O(n²)

An inner loop that multiplies its variable runs log n times, not n:

for i in range(n):   # n times
    j = 1
    while j < n:
        j *= 2       # log₂(n) times

Total: n × log n = O(n log n).

Whenever the inner loop variable is multiplied or divided by a constant instead of incremented, the inner loop is logarithmic. Same halving logic as binary search. For a deeper look, see O(log n) time complexity explained.

The gotcha that has caught many candidates mid-explanation: a sort call hiding inside a loop.

for i in range(n):
    result = sorted(arr)   # O(n log n) per outer iteration

That's O(n² log n), not O(n²). The body of the outer loop is not O(1), and its complexity multiplies in. State it explicitly.

Three Loops Get You O(n³)

Three independent loops over n give you n³. Naive matrix multiplication is the canonical example:

function matMul(A: number[][], B: number[][], n: number): number[][] {
  const C = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return C;
}

The dependent-bound argument extends here too. A triple loop where each inner bound equals the outer variable produces n(n-1)(n-2)/6. Still O(n³).

O(n³) shows up in Floyd-Warshall, certain DP problems with three-dimensional state, and brute-force subset comparison. For n up to a few hundred it's often fine. For n in the thousands it usually isn't, and the interviewer set the constraint knowing that.

Early Exit Doesn't Save Your Worst Case

def contains_duplicate(arr: list[int]) -> bool:
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

Best case: duplicates at indices 0 and 1, function returns after one inner step. Worst case: no duplicates exist, so every iteration runs. That's n(n-1)/2 total. Worst-case complexity is O(n²).

"But it might exit early!" is not an argument for a better complexity class. It's an argument for a better best case. Interviews default to worst case unless they explicitly ask for average or expected complexity. Worst case is the adversarial guarantee: it's what matters for SLA reasoning and what interviewers mean when they say "what's the complexity?"

State both: "Worst case O(n²) because the array could have no duplicates. Best case O(1) if a duplicate appears at the front." One sentence. The clarification shows you understand the distinction.

How to Analyze Any Nested Loop in 30 Seconds

Work from outside in:

Identify what drives each loop. Is it n? Two separate dimensions m and n? The length of a particular array? Name the variable.
Ask if the inner bound depends on the outer variable. If not, it runs a fixed number of times per outer step. If yes, you need to sum across outer steps.
Sum or multiply. Independent bounds: multiply. Dependent bounds: sum the series (triangular for linear dependence, geometric for exponential).
Multiply by the body's complexity. If the body calls a function, what does it cost? O(1) is common but not guaranteed.
State the result with the case. "This is O(n²) worst case because the inner loop runs at most n times for each of the n outer steps."

Here's the process on a real example:

def find_pair(arr: list[int], target: int) -> bool:
    for i in range(len(arr)):             # n iterations
        for j in range(i + 1, len(arr)):  # 0..n-1-i iterations
            if arr[i] + arr[j] == target:
                return True
    return False

Outer: n iterations. Inner: depends on outer, sums to n(n-1)/2. Body: O(1). Worst case (no matching pair): O(n²). Now the follow-up writes itself: replace the inner loop with a hash set lookup and you get O(n) time at O(n) space.

Time complexity analysis in an interview is about reasoning out loud. An interviewer who hears you count iterations scores you higher than one who hears only the final answer, even when both answers are identical.

O(n²) Means Look for a Better Approach

In interviews, identifying O(n²) is usually not the endpoint. It's the setup for the follow-up: can you do better?

Two classic rewrites:

Sliding window turns nested loops over contiguous subarrays into a single O(n) pass. Instead of recomputing every window from scratch, you maintain a running total. See sliding window algorithm for the full technique.
Hash maps eliminate inner search loops. Instead of scanning for a match at O(n) per outer step, you build a map on the first pass and look up in O(1). Two Sum is the textbook example.

When you flag O(n²) as too slow for the given constraint, you force exactly that conversation. For n up to 10³ or 10⁴, it's usually fine. For n at 10⁵ or 10⁶, you need O(n log n) or O(n). Stating the constraint explicitly shows you understand why complexity analysis matters, not just how to run it.

Code review comment on a nested loop brute force solution for all substrings: "there's no way this answer is acceptable, it's literally just brute forcing the problem"

The comment section on brute force interview submissions. Every time.

If you want to practice explaining complexity under real interview pressure, SpaceComplexity runs voice-based mock interviews with rubric feedback on your reasoning, not just your final answer.