Why Every Programmer Should Understand Big-O Notation

In 2021, a programmer known as t0st got tired of waiting for GTA Online to load. Load times of several minutes were common. Instead of blaming the network, t0st profiled the game and found the real culprit: code that processed a JSON file of about 63,000 items in a way that took quadratic time.

The fix was a few lines of code. Load times dropped by about 70%. Rockstar Games patched it and paid t0st a $10,000 bug bounty. The difference wasn't faster hardware. It was Big-O.

A Faster Computer Won't Save a Slow Algorithm

When code is slow, it's tempting to reach for better hardware. For small inputs, that works. For large inputs, the growth rate of an algorithm swamps any constant speedup.

Suppose a computer does 1 billion simple operations per second. Here's how long different algorithms take on 1 million items:

A computer 1,000 times faster would bring the O(n²) algorithm down to about one second. Switching to an O(n log n) algorithm on the original machine is still 50 times faster than that.

What Big-O Actually Measures

Big-O notation describes how an algorithm's running time (or memory use) grows as the input size n grows. It ignores constant factors and small terms, keeping only the dominant behavior.

Formally, f(n) = O(g(n)) means there are constants c and n₀ such that:

f(n) ≤ c · g(n)   for all n ≥ n₀

In plain English: beyond some input size, f grows no faster than g, up to a constant multiple. So:

3n² + 50n + 7 = O(n²)

For large n, the 3n² term dominates everything else.

The Common Complexity Classes

O(1): Constant

Accessing an array element by index, or looking up a key in a hash table (on average). Time doesn't depend on n.

O(log n): Logarithmic

Binary search halves the search range every step. Searching a sorted list of a billion items takes at most about 30 comparisons, because 2³⁰ ≈ 1.07 billion. See how slowly logs grow with the base-2 logarithm table.

O(n): Linear

Looping over every item once: finding a maximum, summing a list.

O(n log n): Linearithmic

Efficient comparison sorts like merge sort and (on average) quicksort. It's been proved that no comparison-based sort can do better in the worst case: sorting n items requires at least log₂(n!) ≈ n log₂ n comparisons.

O(n²): Quadratic

A loop inside a loop over the same data, such as comparing every pair of items. Fine for 100 items (10,000 steps), painful for 100,000 (10 billion steps).

O(2ⁿ): Exponential

Trying every subset of n items. At n = 60, that's over a quintillion possibilities.

How to Estimate Big-O From Code

def has_duplicate(items):
    for i in range(len(items)):          # n times
        for j in range(i + 1, len(items)):   # up to n times
            if items[i] == items[j]:
                return True
    return False

Two nested loops over n items → about n²/2 comparisons → O(n²).

Now the same task with a set:

def has_duplicate(items):
    seen = set()
    for item in items:          # n times
        if item in seen:        # O(1) on average
            return True
        seen.add(item)
    return False

One loop with constant-time lookups → O(n). For a million items, that's the difference between about 500 billion comparisons and 1 million.

An Insider Reference: Where the Notation Came From

The "O" comes from number theory, not computer science. German mathematician Paul Bachmann introduced it in 1894 in a book on analytic number theory, and Edmund Landau popularized it, which is why it's also called Landau notation.

Computer scientists adopted it decades later. In 1976, Donald Knuth published "Big Omicron and Big Omega and Big Theta" in SIGACT News, standardizing three related symbols:

• O (Big-O): an upper bound, "grows no faster than"
• Ω (Big-Omega): a lower bound, "grows at least as fast as"
• Θ (Big-Theta): a tight bound, "grows exactly as fast as, up to constants"

When programmers casually say "this is O(n)," they often mean Θ(n).

Why Constants Still Matter Sometimes

Big-O is a tool for growth, not a stopwatch. For small inputs, an O(n²) algorithm with a tiny constant can beat an O(n log n) one. That's why many standard library sorts switch to insertion sort (O(n²)) for small subarrays inside a faster overall algorithm. Big-O tells you what happens as data grows, and data almost always grows.

Two Concepts Worth Knowing

Logarithm

A logarithm answers "how many times do I multiply (or divide) by the base?" log₂(1,000,000) ≈ 20 means you can halve a million about 20 times before reaching 1. That's why halving algorithms are so fast. Compute logs with the logarithm calculator.

Amortized Analysis

Amortized analysis averages cost over many operations. Appending to a dynamic array occasionally requires copying everything (O(n)), but because capacity doubles each time, the average cost per append is O(1).

Quick Answer: What Is Big-O Notation?

Big-O notation describes how an algorithm's running time or memory grows as input size increases, ignoring constants and lower-order terms. For example, binary search is O(log n), a single loop is O(n), efficient sorting is O(n log n), and nested loops over the same data are O(n²).

Try Them Yourself

• Base-2 Logarithm Table: how many halvings a search needs
• Logarithm Calculator: compute n log n for your data size
• Scientific Calculator: compare n² and 2ⁿ as n grows
• Square Numbers List: feel how fast n² grows
• Numbers API: number facts you can call from your own code
• Alan Turing and the Turing Machine: the theory of computation

Find the slowest function in a project you're working on and write down its Big-O. If it's O(n²) on data that's growing, you may have just found your next big performance win.