Space Complexity and Choosing a Solution

Memory counts too

Space complexity is how much extra memory your code needs as the input grows. It uses the same Big-O language.

def reverse_copy(items):
    result = []                 # a new list of size n  -> O(n) extra space
    for x in items:
        result.insert(0, x)
    return result

def reverse_in_place(items):
    left, right = 0, len(items) - 1
    while left < right:         # only two variables  -> O(1) extra space
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1
    return items

print(reverse_copy([1, 2, 3, 4]))
print(reverse_in_place([1, 2, 3, 4]))

Output

[4, 3, 2, 1]
[4, 3, 2, 1]

Two ways to solve one problem

Problem: does a list contain the same number twice?

def has_duplicate_slow(items):
    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):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

data = [5, 1, 9, 3, 9, 2]
print(has_duplicate_slow(data), has_duplicate_fast(data))

Output

True True

The fast version spends a little memory to save a lot of time. This kind of trade-off comes up again and again in DSA.

Best, average and worst case

Searching a list for a value might be lucky (it's the first item) or unlucky (it's missing). When people say an algorithm is O(n), they usually mean the worst case, so you know the most it can ever cost.

Common mistake: Don't optimise too early. For 10 items any solution is instant. Big-O matters when inputs get large.