How to Analyse Time Complexity of Code (Step by Step)

To find the time complexity of code, ask one question: how many times does the most repeated line run, as a function of n? Then simplify with the Big O rules.

A single loop: O(n)#

def total(items):
    result = 0
    for x in items:       # runs n times
        result += x       # O(1) each time
    return result

print(total([4, 8, 15, 16, 23, 42]))

108

The loop body is constant work and it runs once per item: n × O(1) = O(n).

Sequential steps add up#

def stats(items):
    smallest = min(items)        # O(n)
    largest = max(items)         # O(n)
    first = items[0]             # O(1)
    return smallest, largest, first

print(stats([7, 2, 9, 4]))

(2, 9, 7)

O(n) + O(n) + O(1) = O(2n + 1) = O(n). Steps that happen one after another are added, then simplified.

Nested loops multiply#

def has_duplicate(items):
    for i in range(len(items)):              # n times
        for j in range(i + 1, len(items)):   # up to n times
            if items[i] == items[j]:
                return True
    return False

print(has_duplicate([3, 1, 4, 1, 5]))
print(has_duplicate([2, 7, 1, 8]))

True
False

For each of the n outer iterations, the inner loop runs up to n times: O(n²). Loops inside loops multiply.

A set solves the same problem in O(n), because checking x in seen is O(1) on average:

def has_duplicate_fast(items):
    seen = set()
    for x in items:          # n times
        if x in seen:        # O(1) on average
            return True
        seen.add(x)
    return False

print(has_duplicate_fast([3, 1, 4, 1, 5]))

True

Trading a little memory for a lot of speed like this is one of the most common moves in DSA.

Halving loops: O(log n)#

When each step halves what is left, the loop runs about log₂ n times:

def halvings(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

for n in [16, 1024, 1_000_000]:
    print(n, halvings(n))

16 4
1024 10
1000000 19

A million only needs 19 halvings. This is why binary search is so fast.

Loops that do not depend on n: O(1)#

def first_three_sum(items):
    total = 0
    for i in range(3):     # always 3 times
        total += items[i]
    return total

The loop runs 3 times whether the list has 3 items or 3 million: O(1).

Different inputs keep different letters#

def common(a, b):
    b_set = set(b)                      # O(m)
    return [x for x in a if x in b_set] # O(n)

print(common([1, 2, 3, 4], [3, 4, 5]))

[3, 4]

With len(a) = n and len(b) = m, this is O(n + m). Do not merge them into a single n unless they are the same size.

The cost of Python built-ins#

Built-in operations hide loops. These are the costs to remember:

"Amortized" means occasionally one call is slow, but averaged over many calls each is O(1). You will see why in Arrays and Dynamic Arrays.

Common mistakes#

Practice#

def f1(items):
    i = 1
    while i < len(items):
        i *= 2
    return i

def f2(items):
    count = 0
    for x in items:
        i = len(items)
        while i > 0:
            i //= 2
            count += 1
    return count

def f3(items):
    return sorted(items)[0]

def f2(items):
    count = 0
    for x in items:
        i = len(items)
        while i > 0:
            i //= 2
            count += 1
    return count

for n in [8, 16, 1024]:
    print(n, f2(range(n)))

8 32
16 80
1024 11264

Key takeaway#

Next: memory matters too. See Space Complexity.