Big O Notation

Q: What is the difference between O, Omega and Theta?

Big O is an upper bound: $f$ grows no faster than $g$. Omega, written $\Omega$, is a lower bound: $f$ grows at least as fast as $g$. Theta, written $\Theta$, is a tight bound: $f$ is both $O$ and $\Omega$ of the same $g(n)$, so it grows at the same rate, up to constant factors.

Q: Is an $O(n)$ method always faster than an $O(n^{2})$ method?

Not for small inputs. At $n = 10$, an $n^{2}$ method with a small constant can finish first. For large $n$ the $O(n)$ method wins, because its growth is much slower.

In one sentence: Big O notation is a way to say that one function never grows faster than another, once the input is big enough.

$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \text{ such that } 0 \le f(n) \le c\, g(n) \text{ for all } n \ge n_0$

Read it out loud: “f of n is big O of g of n, if and only if, there exists a positive constant c and a starting point n sub 0, such that for every whole number n that is at least n sub 0, zero is less than or equal to f of n, and f of n is less than or equal to c times g of n. Here f of n is a count of steps, n is the size of the input, and g of n is a simpler reference function such as n.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Functions and the input size $n$: A function is a rule that takes an input and gives back one number. Here $f(n)$ is the number of basic steps an algorithm takes when its input has size $n$ . The input size $n$ is a count of items, such as 10 names in a list or 1000 photos. The notation $f(n)$ is read ‘f of n’, meaning f applied to n.
Powers, like $n^{2}$ and $n^{3}$: A small raised number is an exponent, and it says how many times to multiply a number by itself. So $n^{2} = n \times n$ , read n squared, and $n^{3} = n \times n \times n$ , read n cubed. For $n = 10$ , $n^{2} = 100$ . For $n = 1000$ , $n^{2} = 1000000$ , which is a thousand times bigger than $n$ itself.
The logarithm $\log n$: A logarithm answers the question: how many times can I divide by a number before I reach 1? Here $\log n$ means base 2, so it counts how many times $n$ can be cut in half before reaching 1. For example $\log_2 8 = 3$ , because 8 halved three times gives 4, then 2, then 1. Big O does not care about the base, because changing the base only multiplies by a fixed constant.
The signs $\exists$ , $\iff$ and $\le$: $\exists$ means ‘there exists’, which says that at least one choice works. $\iff$ means ‘if and only if’: the statement on the left is true exactly when the statement on the right is true, in both directions. $\le$ means ‘less than or equal to’, and $\ge$ means ‘greater than or equal to’. So $5 \le 5$ is true, because the two sides are equal.
Steps of an algorithm: An algorithm is a recipe a computer follows, one small step at a time, such as comparing two numbers, adding two numbers or reading one item. Counting steps is the usual way to measure running time, because the same number of steps takes about the same time on a given machine. Big O counts how the number of steps grows, not how many seconds pass.
Constants $c$ and $n_0$: A constant is a fixed number that does not change as $n$ grows. The letter $c$ is a constant multiplier that scales $g(n)$ up. The letter $n_0$ is a starting point, a fixed input size after which the rule must hold. A bigger $c$ or a bigger $n_0$ only makes the rule easier to satisfy, so the definition asks only that some choice exists.

What each symbol means

Symbol	Meaning
$f(n)$	The function you want to measure, such as the number of basic steps an algorithm takes on an input of size $n$ . It counts steps, so it has no unit of its own. For example, an algorithm that does $3n + 5$ steps on 10 items takes $3 \times 10 + 5 = 35$ steps.
$g(n)$	The simpler reference function you compare against, such as $n$ , $n^{2}$ or $\log n$ . It is also a count, and it is chosen to be as simple as possible so the shape of growth is easy to read. When $g(n) = n$ , the comparison is with a straight line, where doubling the input doubles the reference.
$O(g(n))$	Read ‘big O of g of n’. It is the set of all functions that stay below a fixed multiple of $g(n)$ once $n$ is large enough. It is a set of functions, so it has no unit. Saying that $f(n)$ is in $O(n)$ means $f$ stays under some fixed multiple of $n$ for large $n$ .
$n$	The size of the input, a whole number that counts items: how many names are in a list, or how many pixels are in a photo. It has no unit, it is never negative, and it can grow without limit. Typical textbook values are 10, 100 or 1000.
$c$	A positive constant, a fixed multiplier such as 4 that scales $g(n)$ up so that it sits above $f(n)$ . It has no unit and does not depend on $n$ . Once a value of $c$ is chosen, it stays the same for every input size. Any bigger value that works is also allowed.
$n_0$	Read ‘n sub zero’. It is a starting point, a fixed whole number such as 5. The inequality only has to hold for each $n$ at or beyond $n_0$ , so small inputs with odd behavior are ignored. It has no unit.
$\iff$	Read ‘if and only if’. It joins two claims that say the same thing in both directions. The left statement and the right statement are both true, or both false. It has no unit and no numeric value.
$\exists$	Read ‘there exists’. It says that at least one choice of $c$ and $n_0$ makes the rule true. It does not say how many choices work, only that one does. It has no unit and no numeric value.

The formula piece by piece

$n$: The input size, the one number that the step count depends on. As $n$ grows from 10 to 100 to 1000, the work of a growing algorithm grows along with it, and that growth is what big O describes.
$g(n)$: The simple reference shape, such as $n$ , which is a straight line, or $n^{2}$ , which is a curve that bends up faster. It is the yardstick that $f(n)$ is compared against, and it is chosen to be as simple as possible.
$c\, g(n)$: The yardstick scaled up by the constant $c$ . Multiplying by $c$ can lift the yardstick above $f(n)$ , so a factor of 3 or 100 in front of $n$ does not change the shape. Any positive $c$ that works is allowed.
$0 \le f(n) \le c\, g(n)$: The sandwich: $f(n)$ is at least 0, and it is at most the scaled yardstick. Both parts must hold for every $n$ that is large enough. The left part is easy to satisfy, because a step count is never negative.
$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \text{ such that } 0 \le f(n) \le c\, g(n) \text{ for all } n \ge n_0$: In one plain sentence: the function $f(n)$ is big O of $g(n)$ exactly when there is some positive constant $c$ and some starting point $n_0$ , so that for every input at or beyond $n_0$ , $f(n)$ is at least 0 and at most $c$ times $g(n)$ .

What the formula is doing, and why

What goes in and what comes out. Big O notation takes a step-counting function $f(n)$ and a simpler reference $g(n)$ . It answers one question: does $f$ stay below some fixed multiple of $g$ as the input gets big? The answer is yes or no, and we write a yes as $f(n) = O(g(n))$ . The notation describes the shape of growth, not an exact number of steps. The letter O stands for ‘order’, as in the order of growth.

Why the shape, not the exact count? An algorithm that takes $3n + 5$ steps and one that takes $3n$ steps both grow in a straight line as $n$ grows. Both are $O(n)$ . The exact numbers depend on the machine, the language and the details of the code, but the shape stays the same. Big O keeps the part that stays the same across machines.

Why drop constants and small terms? The constant $c$ absorbs any fixed multiplier, so $3n$ and $100n$ both count as $O(n)$ . Smaller terms are dropped for the same reason. For large $n$ , the biggest term decides almost everything. Take $n^{2} + 1000n$ . At $n = 10,000$ , the term $n^{2}$ is 100,000,000, while $1000n$ is only 10,000,000. The $n^{2}$ term is 10 times bigger, so the class is $O(n^{2})$ .

Why the starting point and the bound? The starting point $n_0$ lets you ignore small inputs, where the exact behavior can look different. Together, the constant $c$ and the starting point $n_0$ say that past some point, $f$ never climbs above a fixed multiple of $g$ . This is an upper bound. It limits how fast $f$ can grow, and it says nothing about how fast $f$ must grow.

Why it helps you choose algorithms. An $O(n \log n)$ method beats an $O(n^{2})$ method on large inputs, even when the $O(n^{2})$ method has a smaller constant. Constants and small inputs still matter in practice, so big O is the first comparison, not the last. Big O says nothing about tiny inputs, where a simple $O(n^{2})$ method can be faster.

An everyday picture

Think of making sandwiches for a party. Suppose each sandwich takes about 3 minutes of work, plus a 5-minute setup at the start. Twice as many guests then takes about twice as much work, so the time forms a straight line. That line is the shape, and the job is $O(n)$ , where $n$ is the number of guests. Whether each sandwich takes 3 minutes or 4, and whether the setup takes 5 minutes or 10, the line has the same shape. Big O asks only about the shape, not the exact count.

Worked example: Showing 3n + 5 is O(n)

Let $f(n) = 3n + 5$ be the step count, and let $g(n) = n$ be the reference. Here $n$ is the input size, a count of items such as the number of names in a list. We must find a constant $c > 0$ and a starting point $n_0$ so that $0 \le 3n + 5 \le c \cdot n$ for every $n \ge n_0$ .

Pick a constant. We try $c = 4$ , which is a number bigger than the 3 in front of $n$ . Any constant bigger than 3 can work for large $n$ , because the $+5$ matters less and less as $n$ grows. So 4 is a convenient choice.
Turn the rule into a simple question. We need $3n + 5 \le 4n$ . Subtract $3n$ from both sides, which keeps the inequality true, and we get $5 \le n$ . So the rule holds exactly when $n$ is at least 5.
Choose the starting point. The starting point $n_0 = 5$ works, because for every $n \ge 5$ the condition $5 \le n$ is true. Here is why a starting point is needed: at $n = 1$ , the left side is $3 \cdot 1 + 5 = 8$ , while the right side is $4 \cdot 1 = 4$ , so the rule fails for small inputs.
Check the boundary. At $n = 5$ , the left side is $3 \cdot 5 + 5 = 20$ and the right side is $4 \cdot 5 = 20$ . The two sides are equal. The definition allows this, because it uses $\le$ , less than or equal to, and not a strict less than.
Check a larger input. At $n = 10$ , the left side is $3 \cdot 10 + 5 = 35$ and the right side is $4 \cdot 10 = 40$ , so $35 \le 40$ . At $n = 100$ the left side is 305 and the right side is 400. The gap grows as the input grows, which matches the rule.
Watch the ratio. Divide the step count by $n$ . At $n = 100$ , the ratio is $\frac{305}{100} = 3.05$ . As $n$ grows, $\frac{3n + 5}{n}$ settles toward 3, because the $+5$ becomes less important compared with $3n$ .
Check the lower part. The left part, $0 \le 3n + 5$ , holds for every $n \ge 0$ , because 3 times a count is never negative and adding 5 keeps the result positive. So both parts of the definition are met for $n \ge 5$ .

Answer: With $c = 4$ and $n_0 = 5$ , the definition holds, so $3n + 5$ is O(n). The $+5$ and the factor 3 do not change the shape of the growth, which is a straight line in $n$ .

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Thinking $O(n)$ means exactly $n$ steps. Big O is an upper bound on growth, not an exact count. Both $3n + 5$ steps and $n / 2$ steps are $O(n)$ .
Keeping constants and lower terms in the answer. Write $O(n^{2})$ , not $O(3n^{2} + 5n + 2)$ , and write $O(n)$ , not $O(3n)$ .
Judging small inputs by big O. At $n = 10$ , an $O(n^{2})$ method with a tiny constant can beat an $O(n)$ method with a large one. Big O is about what happens when $n$ is large.
Forgetting to name the case being measured. Big O can describe the best, average or worst case of an algorithm, so say which one, such as worst-case $O(n^{2})$ .

Where you will meet it

Comparing sorting methods, such as merge sort at $O(n \log n)$ and bubble sort at $O(n^{2})$ in the worst case.
Choosing data structures. A hash table lookup takes $O(1)$ time on average, which means a fixed amount of work however big the table is. A search through a plain list takes $O(n)$ time, which grows with the length of the list.
Database indexes, where a B-tree lookup takes $O(\log n)$ time. A B-tree is a tree-shaped index that lets a database find a row quickly, and its work grows slowly as the table gets bigger.
Analyzing loops and recursion in textbooks and programming interviews.

Questions people ask

Why are constant factors ignored?

The constant $c$ absorbs them. A faster computer changes the size of each step, which changes the constant but not the shape of the growth. Big O compares how methods scale as inputs grow, and constant factors depend on the machine, so they are left out.

What is the difference between O, Omega and Theta?

Big O is an upper bound: $f$ grows no faster than $g$ . Omega, written $\Omega$ , is a lower bound: $f$ grows at least as fast as $g$ . Theta, written $\Theta$ , is a tight bound: $f$ is both $O$ and $\Omega$ of the same $g(n)$ , so it grows at the same rate, up to constant factors.

Is an $O(n)$ method always faster than an $O(n^{2})$ method?

Not for small inputs. At $n = 10$ , an $n^{2}$ method with a small constant can finish first. For large $n$ the $O(n)$ method wins, because its growth is much slower.

Master Theorem: The master theorem tells you how long a program takes when it cuts a problem into smaller pieces, solves each piece and joins the answers.
Sum of the First n Integers: This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.
Geometric Series: A geometric series adds up a list where each term is the one before it times a fixed number, and this formula finds the whole sum in one step.
Binary Search Steps: Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.