Big-O Notation

What is Big-O notation?

Big-O notation is a way to say how fast the work of an algorithm grows as its input gets bigger, without counting seconds. Seconds depend on the computer, the language and the day; the number of basic steps as a function of the input size n does not. If an algorithm takes f(n) steps, we write f(n)=O(g(n)) when f grows no faster than g, up to a constant factor.

The definition. f(n)=O(g(n)) means that there are constants c>0 and n_0 such that f(n)\le c· g(n)\qquadfor all n\ge n_0. The pair (c,n_0) is a witness. For example, f(n)=3n^2+5n+7 is O(n^2) with the witness c=4, n_0=7: for n\ge7 we have n^2-5n-7\ge0 (at n=7 it is 7, and it only grows), that is 5n+7\le n^2, so 3n^2+5n+7\le4n^2. A different c gives a different n_0: with c=3 there is none, because 3n^2+5n+7>3n^2 always; with c=100 the inequality holds from n_0=1.

What it throws away. Constant factors (3n^2 and 50n^2 are both O(n^2)) and lower-order terms (n^2+1000n is O(n^2)), because the machine decides the first and the biggest term decides the second when n is large. Two rules follow: the sum of a few functions is dominated by the fastest, and a product multiplies: O(n)+O(n^2)=O(n^2) and O(n)· O(\log n)=O(n\log n).

Three symbols. O is an upper bound ("at most this fast a growth"), \Omega is a lower bound (f(n)\ge c g(n) for large n) and \Theta is both: f=\Theta(g) means f=O(g) and g=O(f). Linear search is O(n), but also O(n^2) and O(2^n), which are true and useless; the useful statement is the tight one, \Theta(n) in the worst case. When the limit of (f(n))/(g(n)) exists, it decides: a finite limit gives f=O(g), a non-zero finite limit gives f=\Theta(g), and a limit of 0 means f grows strictly slower (this is where L'Hôpital's Rule is used).

Try the definition below. Type two functions with n written as x, choose c, and the widget finds the threshold n_0.

How fast do the common growth rates grow?

A handful of classes cover almost every algorithm you meet, and each is a different world of what is feasible. From slowest to fastest growth:

The order is 1≪\log n≪√ n≪ n≪ n\log n ≪ n^2≪ n^3≪2^n≪ n!, where f≪ g means \frac fg→0; the same comparison of growth, a logarithm below any power below an exponential, is proved with limits in the article on growth rates and L'Hôpital's Rule.

What the classes mean in time. Take a computer that does 10^9 steps a second. For n=100 a quadratic algorithm needs 10^4 steps, ten microseconds. An exponential one needs 2^100≈1.3×10^30 steps, which is about 4×10^13 years, thousands of times the age of the universe. And the largest input that finishes in one second is about 10^9 for n, 4×10^7 for n\log n, 31 622 for n^2, 1000 for n^3, only 29 for 2^n and 12 for n!. A computer a thousand times faster adds only 10 to the n of an exponential algorithm (2^10≈1000), while it multiplies the n of a linear one by a thousand. That is why the class matters more than the machine.

Slide n and the speed below. The table gives the steps, the time and the largest n for a time budget.

How do you find the time complexity of code?

You count basic steps, then keep only the term that grows fastest. A few rules cover most code:

1. A basic operation costs 1: an assignment, a comparison, an arithmetic operation, reading an array element.
2. Statements in sequence add, and the biggest wins: a loop of n steps followed by a loop of n^2 steps is O(n+n^2)=O(n^2).
3. A loop multiplies: the number of iterations times the cost of the body. Two nested loops over n cost n· n=n^2.
4. A triangular double loop (j from i+1 to n) runs \fracn(n-1)2 times, which is still O(n^2).
5. A loop that halves or doubles its counter runs \log_2n times: while n > 1: n //= 2 takes \lfloor\log_2n\rfloor steps, and so does i *= 2 while i < n.
6. A loop to √ n (while i * i <= n) runs \lfloor√ n\rfloor times.
7. A recursive function gives a recurrence, solved in the next sections; two recursive calls of size n-1 give 2^n.
8. A condition costs the more expensive branch, when you want the worst case.

Counting by experiment. A good habit is to let the program count its own steps and to double n: if the count doubles the algorithm is linear; if it quadruples, quadratic; if it grows by a constant, logarithmic; if it multiplies by a little more than two, it is n\log n. The widget below runs twelve algorithms on a worst-case input, and the column of ratios shows exactly this.

def first(a):                 # O(1): one step, whatever the length
    return a[0]


def total(a):                 # O(n): one pass
    s = 0
    for x in a:
        s += x
    return s


def pairs(a):                 # O(n^2): n(n - 1)/2 pairs
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            count += 1
    return count


def powers(n):                # O(log n): i doubles until it passes n
    i = 1
    while i < n:
        i *= 2
    return i


def is_prime(n):              # O(sqrt n) divisions, but exponential in the number of digits of n
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n > 1

What are best, worst and average case, and amortized cost?

The same algorithm can cost different amounts on different inputs of the same size, so a complexity is always stated for a case: the best, the worst, or the average. By default "the complexity" means the worst case, because it is a guarantee.

• Linear search for a value in a list of n: best 1 comparison (the first element), worst n (it is last or missing), average about (n+1)/(2) if it is present and every position is equally likely. Best \Theta(1), worst and average \Theta(n).
• Insertion sort: best case n-1 comparisons (already sorted), worst case (n(n-1))/(2) (reversed). The same code is O(n) or O(n^2) depending on the input.
• Quicksort: average O(n\log n), but O(n^2) in the worst case, when the pivots are always the smallest or largest element.
• A hash table lookup: O(1) on average and O(n) if every key collides.

Amortized cost. Some operations are usually cheap and occasionally expensive, and what matters is the total over a long sequence. A dynamic array (a Python list, a C++ vector) doubles its capacity when it is full: the copies cost 1+2+4+…+2^k<2·2^k, so n appends cost fewer than 3n steps in all, and each append is O(1) amortized although one of them costs O(n).

Space complexity is the same idea for memory: merge sort needs O(n) extra space, an in-place sort like heapsort O(1), and a recursion of depth d uses O(d) stack. Big-O describes memory just as it describes time.

Lower bounds. \Omega can show that no algorithm does better. Sorting by comparisons needs at least \log_2(n!)≈ n\log_2n-1.44n comparisons, because the n! possible orders must be told apart by yes-or-no answers, so \Omega(n\log n); merge sort reaches it, and is therefore \Theta(n\log n) and optimal among comparison sorts.

How do you solve the recurrence of a recursive algorithm?

A recursive algorithm that splits a problem of size n into a subproblems of size n/b and does n^d work to split and combine has the cost T(n)=aT(n/b)+n^d, and the Master theorem solves it by comparing d with \log_ba.

Merge sort, unrolled. T(n)=2T(n/2)+n. The top level does n work. The next level has 2 problems of size n/2, doing \frac n2 each, again n in all; the level after that has 4 problems of size \frac n4, again n. Every level costs n, and there are \log_2n levels (halving n down to 1), so T(n)=n\log_2n+n=\Theta(n\log n).

The Master theorem. For T(n)=aT(n/b)+\Theta(n^d) with a\ge1, b>1 and d\ge0, let \rho=(a)/(b^d) be the ratio of the work on one level to the work on the level above: - if d>\log_ba (\rho<1) the work shrinks down the tree and the top dominates: T(n)=\Theta(n^d); - if d=\log_ba (\rho=1) every level costs the same: T(n)=\Theta(n^d\log n); - if d<\log_ba (\rho>1) the work grows down the tree and the leaves dominate: T(n)=\Theta\left(n^\log_ba\right).

For n=b^k the sum is exact: T(b^k)=n^d\left(1+\rho+\rho^2+…+\rho^k\right) when each leaf costs 1, and the three cases are the three behaviors of a geometric series.

Examples. - Binary search: T(n)=T(n/2)+1, so a=1, b=2, d=0=\log_21: \Theta(\log n). - Merge sort: a=b=2, d=1=\log_22: \Theta(n\log n). - Multiplying numbers by Karatsuba: T(n)=3T(n/2)+n, d=1<\log_23≈1.585: \Theta\left(n^1.585\right), better than the school method's n^2. - Multiplying matrices by splitting into 8 blocks: T(n)=8T(n/2)+n^2, \log_28=3>2: \Theta(n^3); Strassen's trick with 7 products, \log_27≈2.807, gives \Theta\left(n^2.807\right). - Halving and then working n: T(n)=T(n/2)+n, d=1>\log_21=0: \Theta(n).

Recurrences that do not have this shape need other methods. T(n)=T(n-1)+n unrolls to (n(n+1))/(2)=\Theta(n^2), and T(n)=T(n-1)+T(n-2)+1, the calls of the naive Fibonacci function, grows like φ^n with φ=\frac1+√52≈1.618.

Choose a, b and d below. The table computes T(n) exactly for n=b^k and divides it by the predicted growth: the last column settles on a constant.

What does Big-O not tell you?

Big-O compares growth for large n, so it says nothing about small inputs, constant factors, memory or the machine.

• Constants matter for small n. 100n is O(n) and n^2 is O(n^2), yet n^2<100n for every n<100. Real sorting libraries are hybrids: Python's and Java's sort (Timsort) use insertion sort, quadratic in the worst case, for short runs, because with a tiny constant it beats n\log n methods below a few dozen elements.
• Not all steps cost the same. A step that misses the processor's cache can cost a hundred times a step that hits it. Two O(n) loops, one reading memory in order and one jumping around, can differ by an order of magnitude.
• What n is. n is the size of the input, the number of bits or digits needed to write it, not its value. Trial division, while i * i <= n, takes O(√ N) divisions to test the number N, but N has n=\log_2N bits (see how many values bits can hold), so the cost is O\left(2^n/2\right): exponential in the size of the input, which is why testing a 600-digit number by trial division is hopeless.
• Hidden costs of operations. x in a_list is O(n) but x in a_set is O(1) on average; s += "a" on a string may copy the whole string; list.insert(0, x) shifts every element, O(n), while list.append(x) is O(1) amortized; sorted(a) is O(n\log n).
• Worst case may not be typical. Quicksort's worst case is n^2 and nobody minds, because it almost never happens with a random pivot.

Use Big-O to choose between a n^2 and an n\log n idea before writing code, and measurement to choose between two ideas of the same class.

How do you measure complexity in code?

Count the steps instead of timing them: a counter is exact, repeatable and independent of the computer. The programs below count the comparisons of linear search, binary search and bubble sort for inputs of 250, 500 and 1000 elements, the calls of the Fibonacci function with and without a memo, and the iterations of a double loop and of a halving loop. Doubling n adds one to the binary search, doubles the linear search and quadruples the bubble sort.

def linear(a, target):
    """Comparisons made while looking for target in a list."""
    steps = 0
    for x in a:
        steps += 1
        if x == target:
            break
    return steps


def binary(a, target):
    """Comparisons made by binary search in a sorted list."""
    lo, hi, steps = 0, len(a) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] == target:
            return steps
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


def bubble(a):
    """Comparisons made by bubble sort."""
    a, steps = list(a), 0
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            steps += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return steps


def fib_calls(n, memo=None):
    """Calls made by fib(n), without and with a dictionary of known values."""
    calls = 0

    def fib(k, known):
        nonlocal calls
        calls += 1
        if k < 2:
            return k
        if known is not None and k in known:
            return known[k]
        value = fib(k - 1, known) + fib(k - 2, known)
        if known is not None:
            known[k] = value
        return value

    fib(n, memo)
    return calls


for n in (250, 500, 1000):
    a = list(range(n))
    print(n, linear(a, -1), binary(a, -1), bubble(a[::-1]))
print(fib_calls(20), fib_calls(20, {}))
print(2 ** 100 / 1e9 / (365.25 * 24 * 3600))
# 250 250 7 31125
# 500 500 8 124750
# 1000 1000 9 499500
# 21891 39
# 40169423537538.64

const count = (f, n) => {
  let steps = 0
  f(n, () => steps++)
  return steps
}
const pairs = (n, tick) => { for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) tick() }
const halving = (n, tick) => { while (n > 1) { n = Math.floor(n / 2); tick() } }
const subsets = (n, tick) => { const go = (i) => { if (i === n) return tick(); go(i + 1); go(i + 1) }; go(0) }
const c = [1000, 2000, 4000].map((n) => count(pairs, n))
c                                           // [499500, 1999000, 7998000]
c.map((v, i) => (i ? v / c[i - 1] : null))  // [null, 4.002..., 4.001...]: doubling n quadruples a quadratic count
;[1e3, 1e6, 1e9].map((n) => count(halving, n))   // [9, 19, 29]: a thousand times more input adds about 10 steps
;[10, 14, 18].map((n) => count(subsets, n))      // [1024, 16384, 262144]: four more elements, sixteen times the work

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
  for (int n = 100; n <= 400; n = n * 2) {
    int pairs = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++) pairs++;           // n(n - 1)/2 steps
    int halves = 0;
    for (int m = n; m > 1; m = m / 2) halves++;          // about log2(n) steps
    printf("%d %d %d\n", n, pairs, halves);
  }
  return 0;
}

/* output:
100 4950 6
200 19900 7
400 79800 8
*/

Where does Big-O notation come from?

Big-O began in number theory, long before computers, as a way to say how big an error term is.

• 1894. The German mathematician Paul Bachmann introduced the letter O in his book on analytic number theory, for the Ordnung, the order, of a term.
• 1909. Edmund Landau used it and added the small o ("grows strictly slower"), and the notation is still often called Landau's.
• 1914. G. H. Hardy and J. E. Littlewood introduced \Omega for a lower bound on growth.
• 1965. Juris Hartmanis and Richard Stearns published On the computational complexity of algorithms, which measured the time of a computation and founded computational complexity theory.
• 1968 and 1976. Donald Knuth used O for the analysis of algorithms in The Art of Computer Programming, and in 1976 redefined \Omega and introduced \Theta as the tight bound, giving the three symbols the meaning they have in computer science today.
• 1971–1972. Stephen Cook and Richard Karp defined NP-completeness, the question of which problems can be solved in polynomial time at all: the line between O(n^k) and exponential that this article drew in the table of growth rates.

What mistakes do people make with Big-O?

The most common mistakes with Big-O are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: Big-O notation at a glance

• Definition: f=O(g) if f(n)\le c g(n) for all n\ge n_0; \Omega is the lower bound, \Theta the tight one.
• Drop constants and lower terms: 3n^2+5n+7=O(n^2).
• Order: 1≪\log n≪√ n≪ n≪ n\log n ≪ n^2≪ n^3≪2^n≪ n!; the class matters more than the machine.
• Counting: sequence adds, loops multiply, halving gives \log n, recursion gives a recurrence; double n and watch the ratio.
• Cases: state best, worst or average; amortized cost spreads rare expensive steps over many cheap ones.
• Master theorem: T(n)=aT(n/b)+n^d compares d with \log_ba: \Theta(n^d), \Theta(n^d\log n) or \Theta(n^\log_ba).
• Limits of Big-O: constants for small n, memory, the size of the input is its digits, and hidden costs of operations.
• Next: a search or a sort with its steps counted.
• Code: count steps with a counter instead of timing.

Glossary: key terms

Big-O notation

A way of saying that a function grows no faster than another, up to a constant factor and for large inputs.

Time complexity

The number of basic steps an algorithm takes, as a function of the size of its input.

Big Theta

A tight bound: a function is both bounded above and bounded below by constant multiples of the same function.

Worst case

The input of a given size on which an algorithm takes the most steps, which gives a guarantee.

Amortized cost

The average cost per operation over a long sequence, when expensive operations are rare and cheap ones are common.

Recurrence relation

An equation that gives the cost of a problem of size n in terms of the cost of smaller problems.

Master theorem

A rule for solving recurrences of the form T(n) = aT(n/b) + n to the d by comparing d with the logarithm of a in base b.

Space complexity

The amount of extra memory an algorithm needs, as a function of the size of its input.

Frequently asked questions

References

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022). Introduction to Algorithms (4th ed.), chapters 3 and 4: Characterizing Running Times; Divide-and-Conquer. MIT Press.
2. Donald E. Knuth (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News 8(2).
3. Juris Hartmanis and Richard E. Stearns (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society 117.
4. Paul Bachmann (1894). Analytische Zahlentheorie. Teubner, Leipzig.

Related articles

• Floating-Point Numbers: How floating-point numbers work: the IEEE 754 bits, spacing and rounding, NaN and infinity, accumulated errors, cancellation, comparisons, and which type to use.
• Indeterminate Forms and L’Hôpital’s Rule: L’Hôpital’s Rule and the indeterminate forms 0/0, ∞/∞, 0·∞, ∞−∞, 1^∞, 0^0 and ∞^0: how to use it, when it fails, and a proof by Cauchy’s theorem, with code.
• Binary Numbers: How Computers Count, Convert and Calculate: Binary numbers explained: bits and place value, converting to decimal and hex, binary arithmetic, two’s complement, bitwise operators and binary fractions.
• Geometric Sequences and Series: Ratio, Sums and Growth: Geometric sequences and series explained: common ratio, the n-th term, finite and infinite sums, geometric means, compound interest and decay, with practice.