Two Nested Loops Do Not Always Mean O(n²)

A common shortcut in interviews is to see a loop inside another loop and immediately call the code quadratic. Sometimes that is right. Often it is not, because what matters is how many times the innermost line actually runs in total, not how many loops you can count on the screen. The four shapes below cover almost every case you will meet.

For each one, count the total work across the whole run of the program.

1) Full Inner Loop - O(n²)

When the inner loop walks the entire input on every pass of the outer loop, the innermost line runs n times for each of n outer passes, which is n * n in total. This is the case the shortcut gets right.

for i in range(n):
    for j in range(n):
        work(i, j)

2) Shared Pointer - O(n)

Here the inner while loop moves a pointer that the outer loop never resets. Across the entire run the pointer can only move forward n times, so the inner loop does at most n steps in total, not n steps per outer pass.

This is the shape behind the two pointer and sliding window techniques.

left = 0
for right in range(n):
    while too_big(left, right):
        left += 1
    work(left, right)

3) Shrinking Inner Loop - O(n²)

When the inner loop starts just after the outer index, it does n - 1 steps, then n - 2, and so on. The total is n(n - 1) / 2. Dropping the constant factor and the lower order term, that is still quadratic.

for i in range(n):
    for j in range(i + 1, n):
        compare(i, j)

4) Doubling Inner Loop - O(n log n)

Here the inner loop variable doubles on every step instead of growing by one.

Starting from 1, you can double only about log₂ n times before passing n.

So every outer pass costs log n steps, and n of those passes cost n log n in total.

for i in range(n):
    step = 1
    while step < n:
        work(i, step)
        step *= 2