How to Analyze Algorithm Complexity

Knowing the names of the complexity classes from Big O notation is only half the skill — the other half is being able to look at a piece of real code and figure out which class it belongs to. The good news is that you don't need a math degree for this. A handful of practical rules get you most of the way there.

The Core Rules

First, count loops, not lines. A single loop over n items is O(n). A loop nested inside another loop, both running over the same n items, is O(n²) — because for every one of the n outer iterations, the inner loop runs n times again. Second, drop constants: an algorithm that does 3n operations is still just O(n), because what matters is the growth shape, not the exact multiplier. Third, drop lower-order terms: if an algorithm does n² + n operations, the n² term dominates for large n, so it's simply O(n²).

Walking Through Real Examples

# Example 1: a single loop
def sum_all(items):
    total = 0
    for item in items:        # runs n times
        total += item          # O(1) work per iteration
    return total
# Total: O(n)

# Example 2: two separate (not nested) loops
def print_twice(items):
    for item in items:        # runs n times
        print(item)
    for item in items:        # runs n times again, but separately
        print(item)
# Total: O(n) + O(n) = O(2n) -> drop the constant -> O(n)

# Example 3: nested loops over the same input
def print_all_pairs(items):
    for a in items:            # runs n times
        for b in items:        # runs n times, for EACH outer iteration
            print(a, b)
# Total: O(n * n) = O(n^2)

# Example 4: loop that halves the problem each time
def count_halvings(n):
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps
# Total: O(log n) -- n is divided, not decremented

Output:

print_all_pairs([1, 2, 3]) prints 9 pairs (3 x 3) — for a 10-item list it would print 100 pairs, and for a 100-item list, 10,000. That's the O(n^2) blowup in action.

A Trickier Case: Sequential vs Nested

The most common mistake beginners make is assuming any two loops in the same function multiply together. They only multiply when one is genuinely inside the other, iterating for every single pass of the outer one — like Example 3. Two loops that simply run one after another (Example 2) just add, and adding two O(n) terms is still O(n), not O(n²). Always ask: "does this inner loop restart completely for every outer iteration?" If yes, multiply. If the loops are separate blocks, add — and then simplify by dropping constants.

Once you can do this analysis quickly, it becomes second nature when reading or writing any function — including the recursive functions covered later in this course, where the same nested-structure thinking applies to the recursion tree instead of loops.

---