Time complexity and big-O notation

Big-O describes how the running time grows as the input grows — not how many seconds something takes on your particular computer.

Big-O	Name	1 000 elements	1 000 000 elements
O(1)	constant	1	1
O(log n)	logarithmic	10	20
O(n)	linear	1 000	1 000 000
O(n log n)	linearithmic	10 000	20 000 000
O(n²)	quadratic	1 000 000	10¹² (too slow)

Constants and smaller terms are dropped: 3n + 50 is O(n), n² + 1000n is O(n²).

def has_duplicates_naive(items):      # O(n²) — two nested loops
    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_duplicates_fast(items):       # O(n) — a set checks in constant time
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

With 10 000 elements: the first makes about 50 million comparisons, the second 10 000. On a million elements the first is entirely impossible while the second takes fractions of a second.

The counting rule: a loop over n is O(n). A loop inside a loop is O(n²). Halving per step is O(log n). Sorting is O(n log n).

In AI: attention is O(T²) in the sequence length — that is why long contexts are expensive, and why alternatives are being researched.