How fast is it? Big O

An algorithm is a precise recipe for solving a problem. Many recipes solve the same problem, and some are enormously faster than others once the input gets big. Timing them in seconds depends on the computer, so instead we count how the number of steps grows as the input size, n, grows.

Big O notation names that growth, ignoring small details and constant factors. The common ones, from fastest to slowest:

O(1), constant: the same steps whatever the size, like reading list[5]. O(log n), logarithmic: each step halves what's left, so a million items take about 20 steps. O(n), linear: look at every item once, like finding the biggest number. O(n log n): good sorting. O(n²), quadratic: compare every item with every other, usually two loops one inside the other.

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

def has_duplicate_fast(xs):     # O(n): a set remembers
    seen = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False

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

The difference is huge in practice. For 100,000 items, O(n) is about 100,000 steps; O(n²) is about 10,000,000,000. Big O usually describes the worst case, and it can measure memory as well as time.