Introduction

Big-O analysis for loops is about counting how many times the loop body executes as input size grows. Many mistakes happen because people focus on syntax shape instead of execution count. A reliable method is to write the iteration equation, simplify dominant terms, and ignore constants.

Core Method for Loop Complexity

For each loop structure:

1. define input size n
2. count body executions
3. express total operations
4. keep dominant growth term

This process avoids guessing and works for single, nested, and mixed loops.

Single Loop Patterns

Linear growth

for i in range(n):
    work()

Body runs n times, so complexity is O(n).

Constant-step increments

1i = 0
2while i < n:
3    work()
4    i += 5

Body runs about n/5 times. Constant divisors are ignored, so complexity is still O(n).

Logarithmic growth

1i = 1
2while i < n:
3    work()
4    i *= 2

i doubles each step. Number of steps is about log2(n), so complexity is O(log n).

Nested Loop Patterns

Quadratic full grid

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

Inner body runs n * n times. Complexity is O(n^2).

Triangular nested loops

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

Total operations are 0 + 1 + 2 + ... + (n-1). Sum is n(n-1)/2, so complexity is O(n^2).

Outer linear, inner logarithmic

1for i in range(n):
2    j = 1
3    while j < n:
4        work()
5        j *= 2

Inner loop is O(log n), repeated n times, so total is O(n log n).

Independent Sequential Loops

Two loops one after another add, not multiply.

1for i in range(n):
2    work_a()
3
4for j in range(n):
5    work_b()

Total is O(n + n), simplified to O(n).

If second loop were O(n^2), total would be O(n + n^2), simplified to O(n^2).

Loops with Shrinking Input

Sometimes inner work depends on remaining input size.

1i = n
2while i > 0:
3    j = i
4    while j > 0:
5        work()
6        j -= 1
7    i //= 2

Cost is n + n/2 + n/4 + ..., a geometric series bounded by 2n. Complexity is O(n).

This is a common interview trap where nested loops still end up linear due to shrinking ranges.

Amortized View for Dynamic Loops

Some loops trigger occasional expensive operations. Example is appending to dynamic arrays that sometimes resize. Single operation may look expensive, but average cost over many operations is constant. In such cases, runtime is amortized O(1) per append and O(n) for n appends.

Understanding amortized analysis helps avoid overestimating complexity from worst-case single events.

Practical Analysis Checklist

When determining Big-O for loops, check these items:

• Is loop counter additive or multiplicative.
• Are loops nested or sequential.
• Does inner bound depend on outer index.
• Does work per iteration change with n.
• Are there early breaks that affect worst-case bound.

Always state whether your answer is worst-case, average-case, or amortized.

Example Walkthrough

1for i in range(n):
2    if i % 2 == 0:
3        for j in range(n):
4            work()

Outer loop runs n times. Inner loop runs only on half of iterations, so about n/2 * n = n^2/2. Constant factor drops, final complexity is O(n^2).

This illustrates why branch frequency usually changes constants, not asymptotic class.

Common Pitfalls

• Multiplying complexities for sequential loops that should be added.
• Forgetting that constant steps do not change Big-O class.
• Treating triangular loops as O(n) instead of O(n^2).
• Ignoring multiplicative counter updates that produce logarithmic loops.
• Mixing worst-case and average-case reasoning in one answer.

Summary

• Big-O for loops comes from execution counts, not visual code shape.
• Add sequential loop costs and multiply nested loop costs.
• Multiplicative counter changes usually imply logarithmic behavior.
• Dominant term determines final asymptotic complexity.
• Use a consistent method and state analysis assumptions clearly.