Introduction

Analyzing the time complexity of a code snippet means counting how the number of operations grows relative to the input size n. The standard tool for this is Big O notation, which describes the upper bound of growth rate, ignoring constant factors and lower-order terms. The key patterns are: single loops are O(n), nested loops are O(n²), halving loops are O(log n), and loops where the inner bound depends on the outer variable require careful summation.

Pattern 1: Single Loop — O(n)

1def sum_array(arr):
2    total = 0
3    for i in range(len(arr)):  # n iterations
4        total += arr[i]        # O(1) per iteration
5    return total
6# Total: O(n)

The loop runs n times, each iteration does constant work.

Pattern 2: Nested Loops — O(n²)

1def print_pairs(arr):
2    n = len(arr)
3    for i in range(n):          # n iterations
4        for j in range(n):      # n iterations each
5            print(arr[i], arr[j])  # O(1)
6# Total: n × n = O(n²)

Each iteration of the outer loop triggers n iterations of the inner loop.

Pattern 3: Nested Loop with Dependent Bound — O(n²)

for i in range(n):
    for j in range(i):  # j goes from 0 to i-1
        print(i, j)

The inner loop runs 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 times total. This is O(n²).

1i=0: 0 iterations
2i=1: 1 iteration
3i=2: 2 iterations
4...
5i=n-1: n-1 iterations
6Total = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)

Pattern 4: Halving Loop — O(log n)

1i = n
2while i > 0:
3    print(i)
4    i = i // 2  # Halves each iteration
5# Iterations: log₂(n)
6# Total: O(log n)

Each iteration halves the value, so it takes log₂(n) steps to reach 0. This is the pattern in binary search.

Pattern 5: Doubling Loop — O(log n)

1i = 1
2while i < n:
3    print(i)
4    i = i * 2  # Doubles each iteration
5# Iterations: log₂(n)
6# Total: O(log n)

Pattern 6: Outer Linear, Inner Logarithmic — O(n log n)

1for i in range(n):          # O(n)
2    j = i
3    while j > 0:
4        j = j // 2          # O(log i) per outer iteration
5# Total: log(1) + log(2) + ... + log(n-1) = O(n log n)

This is the pattern seen in efficient sorting algorithms like merge sort and heap sort.

Pattern 7: Triple Nested Loop — O(n³)

1for i in range(n):
2    for j in range(n):
3        for k in range(n):
4            print(i, j, k)  # O(1)
5# Total: n × n × n = O(n³)

Pattern 8: Loop with Multiplicative Step — O(log n)

1i = 1
2while i < n:
3    print(i)
4    i = i * 3  # Triples each iteration
5# Iterations: log₃(n) = O(log n)

Any multiplicative step (×2, ×3, ×10) produces logarithmic iterations. The base of the logarithm is absorbed into the constant factor in Big O.

Pattern 9: Two Separate Loops — O(n)

1for i in range(n):    # O(n)
2    print(i)
3
4for j in range(n):    # O(n)
5    print(j)
6# Total: O(n) + O(n) = O(n)

Sequential loops add their complexities. O(n) + O(n) = O(2n) = O(n).

Pattern 10: Inner Loop Runs Constant Times — O(n)

1for i in range(n):
2    for j in range(100):   # Always 100 iterations, not dependent on n
3        print(i, j)
4# Total: n × 100 = O(n)

The inner loop runs a fixed number of times regardless of n. Constants are dropped in Big O.

Analyzing a Complex Snippet

1def mystery(n):
2    count = 0
3    for i in range(n):             # O(n)
4        j = 1
5        while j < n:               # O(log n)
6            count += 1
7            j *= 2
8    return count
9
10# Outer: n iterations
11# Inner: log₂(n) iterations each
12# Total: O(n log n)

1def another_mystery(n):
2    count = 0
3    i = n
4    while i > 1:                   # O(log n)
5        for j in range(n):         # O(n)
6            count += 1
7        i = i // 2
8    return count
9
10# Outer: log₂(n) iterations
11# Inner: n iterations each
12# Total: O(n log n)

Space Complexity Quick Reference

1# O(1) space — only uses fixed variables
2def sum_array(arr):
3    total = 0
4    for x in arr:
5        total += x
6    return total
7
8# O(n) space — creates new array
9def double_array(arr):
10    return [x * 2 for x in arr]
11
12# O(n) space — recursive call stack
13def factorial(n):
14    if n <= 1:
15        return 1
16    return n * factorial(n - 1)  # n stack frames

Common Pitfalls

• Ignoring the inner loop's dependency on the outer variable: for j in range(i) inside for i in range(n) is not O(n) — it is O(n²) because the inner iterations sum to n(n-1)/2. Always compute the total by summing across all outer iterations.
• Confusing O(log n) bases: O(log₂ n) and O(log₁₀ n) are the same complexity class because they differ by a constant factor (log₂ n = log₁₀ n / log₁₀ 2). The base does not matter in Big O.
• Assuming nested loops are always O(n²): If the inner loop runs a constant number of times (e.g., for j in range(10)), the total is O(n), not O(n²). Only loops whose bounds grow with n contribute to the complexity.
• Forgetting amortized analysis: Operations like list.append() in Python are O(1) amortized even though occasional resizing is O(n). A loop appending n elements is O(n) total, not O(n²).
• Counting recursive calls incorrectly: A function making two recursive calls with n/2 input each creates 2^(log n) = n total calls (like merge sort), giving O(n log n) with O(n) work per level. Drawing the recursion tree helps visualize the total work.

Summary

• Single loop over n elements: O(n)
• Nested loops with independent bounds: O(n²), O(n³), etc.
• Loop halving or doubling: O(log n)
• Outer O(n) with inner O(log n): O(n log n)
• Dependent inner loops: Sum the iterations (e.g., 0+1+2+...+(n-1) = O(n²))
• Sequential (non-nested) loops add: O(n) + O(m) = O(n + m)
• Constants and lower-order terms are dropped in Big O