What Is Big-O Notation? The Definition and the Rules

Every algorithm question ends with the same follow-up: "what's the complexity?" Most people can answer "O(n)" for a single loop. Fewer can say what the notation actually promises, why 3n + 50 and n get the same label, or why "O(n²)" is a true statement about a linear search. This article builds Big-O from its definition, so the rules stop being folklore and become consequences.

The problem it solves

You want to know whether code will still be fast when the input is a thousand times bigger. A stopwatch cannot tell you:

• Timings depend on the machine, the language, the load and the cache.
• Timings are for one input size. Knowing that 1,000 items take 2 ms says nothing about a million unless you know the shape of the growth.
• Small inputs lie. A big setup cost can lose at n = 10 and win by miles at n = 10⁶.

Big-O answers a different question: as n grows, how does the work grow? Flat, double, quadruple? That shape survives every change of hardware.

The intuition

Count steps instead of seconds, as a function of the input size: f(n). Then compare that function with a simple reference curve g(n) such as 1, log n, n or n².

The formal definition is short. f(n) = O(g(n)) means there are constants c and n0 such that f(n) ≤ c · g(n) for every n ≥ n0. In words: past some starting point, f never grows faster than a constant multiple of g.

Every memorised rule falls out of that sentence:

• Constants drop. 3n is O(n): pick c = 3. The constant multiplier in the definition absorbs any fixed factor.
• Lower terms drop. 3n + 50 ≤ 4n once n ≥ 50, so 3n + 50 is O(n) with c = 4 and n0 = 50. The n0 exists precisely so that small inputs do not count.
• Sequential steps add, then the biggest wins. A loop followed by a nested loop is O(n + n²), which is O(n²).
• Nested steps multiply. A loop of n inside a loop of n is O(n · n).

Big-O is an upper bound, and upper bounds can be loose: a linear search is also O(n²), technically. Two sibling notations close that gap. Big-Omega, Ω(g), is a lower bound: at least a constant times g. Big-Theta, Θ(g), is both at once, a tight bound. When engineers say "it's O(n)", they almost always mean the tight bound.

One more distinction trips people up: best, average and worst case are not the same thing as O, Ω and Θ. The cases pick which input you analyse; the notations describe how that chosen function grows. Linear search's worst case is Θ(n) and its best case is Θ(1).

Watch it run

The animation plots the lesson's loop. Big-O plots work against input size, never seconds and never hardware. A constant-time algorithm comes first and is flat: it does the same work for ten items as for ten million. Then the loop's line rises: at n = 3 it runs 3 times, at n = 8 it runs 8 times, then 14, then 20, and the marker never leaves the diagonal. Double the input and you double the work, and that relationship is the answer. In the last frame a dashed 2n curve appears above n. It sits higher but bends the same way, so constants get dropped and both are just O(n); the readout makes the same point about 3n + 50.

The code

Counting operations instead of timing them. The second function costs 3n + 50, and its ratio to the first settles at the constant 3, exactly what Big-O ignores:

def total(nums):
    ops = 0
    s = 0
    for x in nums:              # the lesson's loop: one addition per item
        s += x
        ops += 1
    return s, ops

def total_with_setup(nums):
    """The same sum, with 50 steps of setup and 3 steps per item: 3n + 50."""
    ops = 50
    s = 0
    for x in nums:
        s += x
        ops += 3
    return s, ops

for n in (10, 1_000, 100_000):
    _, a = total(range(n))
    _, b = total_with_setup(range(n))
    print(n, a, b, round(b / a, 4))
# 10 10 80 8.0
# 1000 1000 3050 3.05
# 100000 100000 300050 3.0005

# The definition: f(n) = O(g(n)) if f(n) <= c * g(n) for every n >= n0.
f = lambda n: 3 * n + 50
c, n0 = 4, 50
print(all(f(n) <= c * n for n in range(n0, 100_000)))   # True
print(f(49) <= c * 49)                                  # False  below n0 the bound may fail

The doubling test is the practical version: double n and look at the ratio of the work, here for four step counters, including a best and a worst case of one search:

def linear_search(items, target):
    steps = 0
    for x in items:
        steps += 1
        if x == target:
            break
    return steps

def count_pairs(n):
    steps = 0
    for i in range(n):
        for j in range(i + 1, n):   # every pair once: n(n - 1) / 2
            steps += 1
    return steps

def halvings(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

for name, work in [("pairs", count_pairs),
                   ("halving", halvings),
                   ("search, worst", lambda n: linear_search(range(n), -1)),
                   ("search, best", lambda n: linear_search(range(n), 0))]:
    small, big = work(1_000), work(2_000)
    print(f"{name:14} {small:>7} {big:>8}  x{big / small:.2f}")
# pairs           499500  1999000  x4.00
# halving              9       10  x1.11
# search, worst     1000     2000  x2.00
# search, best         1        1  x1.00

Quadratic work quadruples, linear work doubles, logarithmic work adds one step, and constant work does not move. Last, a seeded check of the two rules on 2,000 random polynomials with non-negative coefficients: the witness c = sum of coefficients, n0 = 1 always satisfies the definition, and the rule "keep the highest power" always matches a brute-force estimate of the exponent from the doubling ratio at a large n:

import math
import random

def big_o_degree(coeffs):
    """The rule: drop constants and lower terms, keep the highest power."""
    return max(k for k, a in enumerate(coeffs) if a > 0)

def measured_degree(coeffs, n=10**7):
    """Brute force: how many doublings of the work does doubling n cause?"""
    f = lambda m: sum(a * m**k for k, a in enumerate(coeffs))
    return round(math.log2(f(2 * n) / f(n)))

rng = random.Random(31)
ok = True
for _ in range(2_000):
    coeffs = [rng.randint(0, 1000) for _ in range(rng.randint(1, 5))]
    if not any(coeffs):
        coeffs[0] = 1
    d = big_o_degree(coeffs)
    ok &= d == measured_degree(coeffs)
    c = sum(coeffs)                              # witness: c = sum of coefficients, n0 = 1
    ok &= all(sum(a * n**k for k, a in enumerate(coeffs)) <= c * n**d
              for n in rng.sample(range(1, 10**6), 50))
print(ok)                                        # True

The complexity

The rules, applied the way an interviewer expects you to apply them out loud:

• One loop over the input: O(n). The lesson's total is the canonical case.
• Two loops one after the other: O(n + n) = O(n). Adding does not change the class.
• A loop inside a loop: O(n²), and n(n - 1) / 2 pairs is still O(n²).
• Halve the problem each step: O(log n), which is why binary search barely notices a bigger array. The O(log n) article shows why.
• Two different inputs: keep both names, O(n + m) or O(n · m).

The Big-O cheat sheet lists the classes of common operations side by side.

Where it goes wrong

• Treating Big-O as speed. An O(n log n) sort with a large constant can lose to an O(n²) one on 20 items, which is why real sort implementations switch to insertion sort for small runs.
• Hidden loops. x in some_list, list.pop(0), string concatenation in a loop and slicing are each linear. One of them inside a loop turns O(n) into O(n²).
• Mixing up cases and bounds. "Quick sort is O(n log n)" is only true for the average case; its worst case is Θ(n²).
• Forgetting space. Recursion depth, copies and hash sets are memory, and "and the space?" almost always follows.

When it shows up in interviews

After every coding solution, as "what's the time and space complexity?", and before it, when you compare a brute force with a better idea. The follow-ups test the rules, not the labels: "why do we drop the constant?", "is your solution also O(n²)?", "average or worst case?". The six classes you will name most often are laid out in Big-O complexity classes.

How to say it in an interview

"Big-O describes how the work grows with the input size, ignoring hardware and constant factors. Formally, f is O(g) if past some n0, f stays below a constant times g, which is why constants and lower-order terms disappear: 3n + 50 is O(n). It's an upper bound, so for a tight statement I'd say Theta, and I'd name the case: a one-pass solution with a hash set is Theta of n time in the worst case, plus O(n) extra space."