Analyzing Loops: From Code to Big-O

Algorithms & Complexity

Chapter 3 · Analyzing Loops: From Code to Big-O

Chapter 2 built the math; this chapter is where it gets applied directly to real code. The core technique is almost mechanical once you know the rules: count how many times each line of code runs, as a function of n, then simplify with Chapter 2's own dominant-term rule.

A Single Loop — O(n)

total = 0
for i in range(n):
    total += i

The loop body runs exactly n times, each iteration doing a fixed, constant amount of work. Total: O(n).

Sequential Loops — The Sum Rule

for i in range(n):
    print(i)

for j in range(n):
    print(j)

Sum rule

Two separate (not nested) blocks of code each running n times: total work is n + n = 2n, which the dominant-term rule collapses straight to O(n). Sequential blocks add; the slowest-growing block among them never changes the overall class, only its irrelevant constant.

Nested Loops (Independent Bounds) — The Product Rule

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

Product rule

The inner loop runs n times for each of the outer loop's n iterations: n × n = n² total. Nested blocks multiply. This is exactly Chapter 1's own "innocent-looking nested loop" — two ordinary for loops, quietly O(n²).

Triangular Loops (Dependent Bounds) — Still O(n²)

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

Here the inner bound depends on the outer loop variable — the total operation count is a sum: 0 + 1 + 2 + ... + (n−1). This is exactly the summation Discrete Mathematics Fundamentals Chapter 8 proved a closed form for: Σᵢ₌₀ⁿ⁻¹ i = n(n−1)/2.

Verified with a real n

At n = 6: direct sum 0+1+2+3+4+5 = 15; formula 6×5/2 = 15 — exact match. And n(n−1)/2 simplifies (Chapter 2's own dominant-term rule) to O(n²) — the same class as the fully independent nested loop above, just with roughly half the actual operations.

Gotcha 1: A Constant Inner Bound Is Not O(n²)

for i in range(n):
    for j in range(10):   # fixed, always 10 — not related to n
        print(i, j)

Nesting alone doesn't mean O(n²)

Total operations: n × 10 = 10n. Since 10 is a fixed constant, entirely unrelated to n, this simplifies to O(n), not O(n²) — despite the visible nesting. The product rule only produces a genuinely higher complexity class when both bounds actually grow with n.

Gotcha 2: A Multiplicative Loop Variable Gives O(log n)

i = 1
while i < n:
    i *= 2   # doubling, not incrementing by 1

Because i doubles each iteration rather than simply incrementing, the loop runs far fewer than n times. For n = 1,000,000: this loop runs exactly 20 times before i reaches or exceeds n — matching log₂(1,000,000) ≈ 19.93, and matching Chapter 1's own binary search figure exactly. Whenever a loop variable grows multiplicatively, the complexity is O(log n), not O(n).

Loop Analysis in Code

def count_triangular_operations(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

n = 6
print(count_triangular_operations(n))  # 15
print(n * (n - 1) // 2)             # 15 — matches the closed-form formula exactly

def count_doubling_iterations(n):
    i, count = 1, 0
    while i < n:
        i *= 2
        count += 1
    return count

print(count_doubling_iterations(1_000_000))  # 20

Hands-On Exercises

Exercise 1

A function runs one loop over n items, then (not nested — sequentially afterward) a second loop over a separate, fixed-size list of exactly 50 items, then a third loop over the same n items again. Using this chapter's own sum rule, determine the overall Big-O class, and explain why the 50-item loop doesn't change the final answer.

📄 View solution

Exercise 2

For a triangular loop identical in structure to this chapter's own example, compute the exact total operation count at n = 10 both by direct summation and by the closed-form formula n(n−1)/2, confirming they match. State the resulting Big-O class.

📄 View solution

Exercise 3

A loop starts with i = 1 and triples i (i *= 3) each iteration until i ≥ n. State the Big-O class of this loop, and compute the exact number of iterations it takes to reach or exceed n = 1,000,000.

📄 View solution

Chapter 3 Quick Reference

Method: count operations per line as a function of n, sum them up, simplify with Chapter 2's dominant-term rule
Sum rule: sequential (non-nested) blocks add their complexities — the slowest-growing one wins
Product rule: nested blocks multiply their complexities — n × n = n² for independent bounds
Triangular loops (dependent inner bound) use the summation formula Σi = n(n−1)/2 — still O(n²), just with about half the operations
Gotcha 1: a nested loop with a constant (non-n-dependent) bound stays O(n), not O(n²)
Gotcha 2: a loop variable that grows multiplicatively (doubling, tripling) gives O(log n), not O(n)
Next chapter: Big-Omega and Big-Theta — best, worst, and average case