Introduction

Questions about time complexity are rarely about the number of loops alone. They are about the total number of times the work inside those loops runs. A classic example is a nested-loop function where the inner loop starts from the current outer index. That pattern performs a triangular number of operations, which leads to quadratic time.

Start by Counting Real Work

Consider this function:

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

Many people see two loops and immediately answer O(n^2). In this case the answer is correct, but the route to the answer matters. The inner loop does not always execute n times. Its length shrinks as i increases.

That means we should count total executions of count += 1 rather than guessing from surface structure.

Derive the Exact Count

For each outer iteration:

• when i = 0, the inner loop runs n times
• when i = 1, it runs n - 1 times
• when i = 2, it runs n - 2 times
• when i = n - 1, it runs 1 time

So the exact work is:

n + (n - 1) + (n - 2) + ... + 1

That sum is the well-known arithmetic series:

n(n + 1) / 2

This is a useful habit in algorithm analysis. First derive the exact count when it is easy to do so. Then simplify to asymptotic growth.

Convert the Exact Count to Big O

Expanding the formula gives:

(n^2 + n) / 2

Big O notation ignores constant factors and lower-order terms, so the n^2 term dominates. That gives the final result:

O(n^2)

This explains why the function is quadratic even though the inner loop shrinks. The total still grows proportionally to the square of the input size.

Why the Shrinking Inner Loop Does Not Change the Order

It is tempting to think the decreasing inner loop makes the function significantly cheaper than a full nested loop from 0 to n - 1 in both dimensions. It does reduce the amount of work, but only by a constant factor.

A full square-shaped loop performs about n^2 operations. A triangular loop performs about n^2 / 2 operations.

Those are different exact counts, but they belong to the same asymptotic growth class. Big O deliberately ignores the division by 2.

That is the difference between exact analysis and asymptotic analysis:

• exact count answers "how much work exactly"
• Big O answers "how fast does the work grow"

Both are useful, but they answer different questions.

Validate with a Small Experiment

You can verify the exact pattern with code:

1def example_func(n):
2    count = 0
3    for i in range(n):
4        for j in range(i, n):
5            count += 1
6    return count
7
8for n in range(1, 6):
9    print(n, example_func(n))

The output is:

11 1
22 3
33 6
44 10
55 15

These are triangular numbers, which matches the derived formula n(n + 1) / 2.

Do Not Forget Space Complexity

The function performs a lot of repeated work, but it uses only a fixed amount of extra memory. The loop variables and accumulator do not grow with n.

So the auxiliary space complexity is:

O(1)

Time and space should be analyzed separately. A function can be quadratic in time and still constant in extra memory.

Common Pitfalls

• Declaring any nested loop automatically O(n^2) without checking the loop bounds.
• Confusing the exact count n(n + 1) / 2 with the asymptotic result O(n^2).
• Assuming a shrinking inner loop makes the function linear.
• Ignoring lower-order terms correctly but never identifying the dominant term first.
• Forgetting to analyze space usage along with time complexity.

Summary

• Count how many times the inner work really runs instead of judging by loop count alone.
• This triangular loop pattern executes n(n + 1) / 2 times exactly.
• The dominant growth term is n^2, so the time complexity is O(n^2).
• A smaller constant factor does not change the Big O class.
• The function uses constant extra memory, so its space complexity is O(1).