Working out the complexity of code

Big idea

You can find the Big-O of most code with four rules: steps in sequence add, nested loops multiply, a loop that halves its range is log n, and recursion costs (calls) × (work per call).

Rule 1: sequence adds

for x in nums:        # n
    print(x)
for x in nums:        # n
    for y in nums:    #   × n
        print(x, y)

n + n² = O(n²). When blocks run one after the other, add them and keep the biggest.

Rule 2: nesting multiplies

A loop inside a loop runs the inner body (outer count) × (inner count) times. Watch what the inner loop depends on:

for i in range(n):
    for j in range(i + 1, n):   # n-1, n-2, ..., 1, 0
        compare(nums[i], nums[j])

The inner loop shrinks, but the total is (n−1) + (n−2) + … + 1 = n(n−1)/2 — still O(n²). Checking "every pair" is quadratic whether or not you skip repeats.

Two loops over different inputs stay separate: a loop over n words and an inner loop over each word's m letters is O(n × m), not O(n²).

Watch it

Rule 3: halving is log n

i = n
while i > 0:
    work()
    i //= 2

i goes n, n/2, n/4, …, 1 — about log₂ n iterations. The same holds when i doubles up to n.

A sneaky case: a loop that halves inside a loop over n is O(n log n):

for x in nums:          # n
    j = len(nums)
    while j > 0:        # log n
        j //= 2

Rule 4: recursion — calls × work per call

Draw the call tree. The cost is the number of calls times the work done in each.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Each call makes 2 more, about n levels deep, so there are up to 2ⁿ calls, each doing O(1) work: O(2ⁿ). In general, a recursion with b branches and depth d makes about bᵈ calls.

Compare binary search written recursively: one branch per call, depth log n — O(log n). And merge sort: 2 branches, depth log n, but each level does O(n) merging — O(n log n).

A worked example

def has_duplicate(nums):
    nums.sort()                        # O(n log n)
    for i in range(1, len(nums)):      # O(n)
        if nums[i] == nums[i - 1]:
            return True
    return False

Sequence: n log n + n → O(n log n). A hash set version is O(n): one pass, O(1) per lookup.

Common traps

• Hidden loops. x in my_list, list.index, slicing nums[1:], and string concatenation in a loop each cost O(n). Put one inside a loop and you have O(n²).
• Calling a function in a loop. If helper() is O(n), then for x in nums: helper() is O(n²).
• Assuming two loops mean n². Two loops in sequence are O(n). Only nesting multiplies.

Quick check