What if the inner loop step multiplies by 2?

If the inner variable doubles each step (e.g., $j = j imes 2$ up to $n$), the inner loop runs in $O(\log n)$ time. Multiplied by an $O(n)$ outer loop, the total complexity is $O(n \log n)$.

What if the inner loop bound is a constant limit?

If the inner loop runs a fixed $c$ times regardless of $n$, its complexity is $O(1)$. The total complexity is dictated entirely by the outer loop.

How do you handle three or more nested loops?

Apply the exact same procedure recursively. Set up a nested summation for dependent bounds, or multiply the complexities if all bounds are independent.

How to find the Big O of a nested loop

Determine the time complexity of a nested loop by evaluating the number of iterations for the inner loop and multiplying it by the number of iterations of the outer loop. This applies when evaluating standard iterative algorithms where loop bounds are defined by the input size $n$ .

The setup

Identify the outer loop, the inner loop, and the operations performed inside the deepest nesting level. Define the loop variable bounds and step sizes in terms of the input size $n$ .

The steps

Determine the iteration count of the outer loop as a function of $n$ . 2. Determine the iteration count of the inner loop. 3. If the inner loop bounds are independent of the outer loop, multiply the two counts. If the inner loop depends on the outer loop variable, express the total iterations as a summation over the outer loop variable. 4. Evaluate the summation or multiplication, then drop lower-order terms and constant factors to yield the final $O()$ notation.

Checking the result

Select small integer values for $n$ and trace the loops to count the exact number of innermost executions. Verify that the polynomial degree of the exact count matches the calculated asymptotic complexity.

Common errors

A frequent error is assuming any two nested loops automatically result in $O(n^2)$ complexity. Another common mistake is ignoring step sizes, such as a variable doubling ( $i = i imes 2$ ), which yields logarithmic $O(\log n)$ iterations rather than linear ones.

Worked example

Find the Big O time complexity of a loop where the outer loop variable $i$ goes from 1 to $n$ , and the inner loop variable $j$ goes from 1 to $i$ , with both incrementing by 1.

The outer loop runs $n$ times. For each iteration $i$ , the inner loop runs exactly $i$ times. The total number of operations is expressed by the summation: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}$ . Dropping the constant divisor and the lower-order linear term $\frac{n}{2}$ , the asymptotic time complexity is $O(n^2)$ .

FAQ

Run your own problem

Answer form

References: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) · The Algorithm Design Manual (Skiena)