Big-O in Plain English

Complexity

Big-O describes how runtime grows as the input grows. It ignores constant factors and compares algorithms at scale.

The common classes

Counting operations

def first(a):        # O(1)\n    return a[0]\n\ndef linear(a):       # O(n)\n    for x in a:\n        print(x)\n\ndef pairs(a):         # O(n²)\n    for i in a:\n        for j in a:\n            print(i, j)

The rule of thumb

One loop over the data = O(n). A loop inside a loop = O(n²). Halving each step = O(log n).

Why it matters

# 1,000,000 items:\n# O(n)     -> ~1,000,000 steps\n# O(n log n)-> ~20,000,000 steps\n# O(n²)    -> ~1,000,000,000,000 steps

Space complexity too

Algorithms also use memory. A solution that copies the whole list costs O(n) space. Prefer in-place changes when you can.

Tip: Optimise only after you have a working solution. A clean O(n²) answer that runs is better than a broken O(n) one.