Big-O Notation

By Victor Arce

When we say one algorithm is "faster" than another, we rarely mean on one specific input — we mean how its cost grows as the input gets bigger. Big-O notation captures exactly that: the shape of the growth, ignoring constant factors and small inputs. It's the single most useful idea for comparing algorithms, and every other article here leans on it.

Step through the common complexity classes below. Each one is added to the same axes — input size n across the bottom, work (operations) up the side — so you can watch the curves separate. Near n = 1 they all look similar; the whole point of Big-O is what happens as you move right.

Reading the curves

Big-O is an upper bound on growth, written O(f(n)). It deliberately drops constants and lower-order terms: O(n) and O(3n + 50) are the same class, because once n is large enough the 3 and the 50 stop mattering next to the shape n. What survives is the term that dominates as n → ∞.

From slowest- to fastest-growing, the classes in the animation are:

• O(1) — constant. The work doesn't depend on n at all. Looking up an array element by index, or pushing to a stack.
• O(log n) — logarithmic. Each step throws away a constant fraction of what's left. Binary search checks ~10 items to find one among 1000.
• O(n) — linear. One look at each item. Summing a list, or a single scan.
• O(n log n) — linearithmic. The best you can do for a comparison sort: merge sort, heapsort, quicksort on average.
• O(n²) — quadratic. Roughly every item compared with every other. Bubble, selection and insertion sort on large inputs.
• O(2ⁿ) — exponential. Adding one element doubles the work. Trying every subset of a set — useless beyond tiny n.

Why the class is what matters

A faster computer multiplies your speed by a constant. Moving to a lower complexity class changes the shape of the curve — and at scale, shape beats constants every time. An O(n log n) sort on a slow laptop will crush an O(n²) sort on a supercomputer once n is big enough. That's why, when we analyze the algorithms in the rest of the site, the first question is always "what's its Big-O?"

There are companion bounds worth knowing: Ω (omega) is a lower bound (it takes at least this much), and Θ (theta) is a tight bound (upper and lower match). Big-O is the one you'll reach for most.

Back to Foundations