Python Time and Space Complexity

A complexity claim only makes sense once you say what n is. For a pantry, n might be the number of products, the number of donations, or the length of a product name, and different steps of a program may depend on different sizes:

def has_product(products, name):   # n = len(products)
    for product in products:
        if product == name:
            return True
    return False

Big O keeps the fastest-growing term and drops constants: an algorithm doing 3n + 20 steps is O(n), because for large n the 3 and the 20 stop mattering to the shape of the growth. When there are two independent sizes, keep both: comparing every donation (d) against every product (p) is O(d × p), not O(n²).

Being explicit avoids confusing claims. "This is O(n)" about a function that loops over products and, inside, scans each product's name is really O(p × L), where L is name length; with short names that's effectively linear in p, but the assumption should be stated.

def has_duplicate_slow(items):          # O(n²): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):          # O(n) average: one pass with a set
    return len(set(items)) != len(items)

Big O isn't a stopwatch. It describes growth, not actual seconds: an O(n²) algorithm on 50 items can beat an O(n log n) one with heavy constant overhead. It tells you which approach will fall over as data grows, and that's when it matters most.

The same algorithm can do very different amounts of work depending on the input:

• Best case: searching a list for the first item finds it immediately, 1 check.
• Worst case: searching for an item that isn't there checks all n items.
• Average case: for a random present item, about n/2 checks, which is still O(n).

Big O statements usually describe the worst case unless stated otherwise, because that's the guarantee you can rely on.

Python's sets and dictionaries are O(1) on average for lookups, inserts and deletes, thanks to hashing (see hash tables). That average assumes keys hash well; in pathological cases, many colliding keys, operations degrade towards O(n). In everyday code the average case holds, which is why "use a set for membership tests" is such reliable advice.

Some operations are amortised: list.append() occasionally has to copy the whole list to a bigger block, but averaged over many appends each one is O(1).

Space complexity usually counts the extra memory an algorithm needs beyond its input, called auxiliary space:

def total_quantity(items):        # O(1) extra space: one running total
    total = 0
    for _, qty in items:
        total += qty
    return total

def sorted_names(items):          # O(n) extra space: builds a new list
    return sorted(name for name, _ in items)

Common sources of extra memory are copies (items[:], sorted()), new collections built in a loop or comprehension, sets used for fast lookup, and the call stack in recursive functions: recursion that goes n levels deep uses O(n) stack frames even if each frame is small.

There's often a trade-off: has_duplicate_fast above uses O(n) extra memory for its set to save time, while the slow version uses O(1) space. Choosing between them depends on which resource is scarce. Generators can reduce space dramatically by producing one item at a time instead of building a full list.

Task: analyse an inventory scan, nested pair comparison and dictionary lookup with explicit assumptions and auxiliary memory.

pantry = {"rice": 12, "beans": 0, "oats": 7, "lentils": 3}

def low_stock(pantry, limit):          # O(n) time, O(k) extra space for k results
    return [name for name, qty in pantry.items() if qty < limit]

def similar_pairs(names):              # O(n²) time: every pair
    return [(a, b) for i, a in enumerate(names) for b in names[i + 1:] if a[0] == b[0]]

def quantity(pantry, name):            # O(1) average time, O(1) space
    return pantry.get(name, 0)

print(low_stock(pantry, 5))                        # ['beans', 'lentils']
print(similar_pairs(["rice", "rye", "oats"]))      # [('rice', 'rye')]
print(quantity(pantry, "oats"))                    # 7

State n for each: the number of pantry products. Note that names[i + 1:] also copies part of the list on every iteration, adding memory use. For the worked check, the worst-case growth of a full list scan is O(n).

The Python wiki's TimeComplexity page lists costs for list, deque, set and dict operations. Continue with linear and binary search and sorting algorithms. Practise with the Python exercises and Python quiz.