Big O Notation

What is Big O notation

Big O notation describes how the cost of an algorithm grows as its input grows. It won't tell you that a function takes 3 milliseconds. It tells you what happens to that function when the input goes from a thousand items to a million.

So Big O is about scalability, not raw performance. Two functions can run equally fast on your machine with the test data you have today. Once the real data grows a hundred times bigger, one of them may still be fine and the other may become the reason your page takes ten seconds to load. Big O is how you tell them apart before that happens.

The notation is the letter O followed by a function of n, where n is the size of the input: O(1), O(n), O(n²). You read O(n) as "grows in proportion to n".

Time and space

Every algorithm has two kinds of complexity:

• Time complexity is how the number of operations grows with n.
• Space complexity is how the amount of extra memory the algorithm allocates grows with n.

Extra is the important word there. The input is already in memory before the algorithm runs, so it isn't counted. What counts is whatever the algorithm creates along the way, like a copy of a slice, a map of values it has already seen, or the call stack of a recursive function.

The two are measured separately, and they don't have to match. A function can be O(n) in time and O(1) in space at the same time. Finding the largest number in a slice is a good example:

You can't know which number is the largest without looking at all of them, so the loop visits every element. That makes the time O(n). Memory is a different story: no matter how long the slice is, the function only keeps one extra variable, best. That makes the space O(1).

Here's the same result computed another way:

It returns the right answer, but it's worse on both counts. Sorting makes the time O(n log n), and the copy makes the space O(n). On a slice of ten numbers you'd never notice. On a slice of ten million, the first version wins easily.

Always assume the worst case

When you analyze an algorithm, be pessimistic. Find the input that makes it do the most work and describe that case.

Take a linear search, which walks through a slice until it finds a value. If the value is in the first position, it's done after one comparison. If the value is at the tail, or isn't in the slice at all, it has to compare every element. Big O describes the second situation, so linear search is O(n).

The reason is that the best case doesn't promise anything. "It's fast when the item happens to be first" depends on luck, not on the algorithm. The worst case, on the other hand, is a guarantee: whatever input shows up, the algorithm will never do more work than that. That's the number you want when you're deciding whether something will hold up in production.

And bad inputs are more common than they sound. In the Binary Search Trees article, data that arrives already sorted, which is about as ordinary as data gets, turns every O(log n) operation into O(n).

Scalability, not speed

A better Big O is usually what you want, but it doesn't mean faster. You can't say that an O(n) algorithm is quicker than an O(n²) one. You can only say which one handles growth better.

That's because Big O leaves details out on purpose. Suppose algorithm A does 100n operations and algorithm B does n²:

With fewer than 100 elements, B does less work even though it's the quadratic one. At 100 they tie. After that, A stays ahead for good, and by a million elements B is doing ten thousand times more work.

You can see this in real code. Go's slices.Sort is an O(n log n) algorithm, but once a piece of the slice has 12 elements or fewer, it switches to insertion sort, which is O(n²). For tiny inputs, the simpler algorithm has less overhead and finishes first. Big O only describes what happens as n keeps growing.

Dropping constants and smaller terms

The same idea gives us the two simplification rules you'll see everywhere:

• Drop the constants. 100n, 2n and n / 2 are all O(n). A constant makes the line steeper or flatter, but it's still a straight line: double the input and the work doubles.
• Keep only the biggest term. n² + n is O(n²). With a million elements, n² is a trillion and n is a million, so the smaller term barely registers.

Following the same logic, a fixed amount of work is O(1) even when it's large. Five hundred operations that never change with n are still constant.

The common complexity classes

Most algorithms you'll run into fall into a handful of classes. Here they are on the same chart:

The following sections go through them one at a time, from the flattest curve to the steepest.

O(1): constant

An O(1) operation takes the same time, or the same memory, no matter how big the input is.

Reading the first item of a slice is the simplest example:

The length of nums doesn't matter. The function reads one position and returns. The same goes for reading any index: as the Arrays article explains, the address of nums[i] is calculated with one multiplication and one addition, so nums[999999] costs the same as nums[0]. Checking if a number is even (n%2 == 0) and pushing onto a stack are constant time too.

O(log n): logarithmic

The short version: the input can grow a lot while the cost grows only a little.

The more precise version: when the input grows exponentially, the cost grows linearly. Each time you double n, a logarithmic algorithm needs one more step. Going from a thousand elements to a million, which is a thousand times more data, adds about ten steps.

To see why, it helps to remember what a logarithm is. It's the inverse of a power. 2³ = 8 means "multiply 2 by itself 3 times and you get 8". log₂ 8 = 3 asks the question the other way around: "how many times do I multiply 2 to reach 8?"

In programming there's a more useful way to read it: log₂ n is how many times you can cut n in half before you get to 1. Halve 8 and you get 4, then 2, then 1. That's three halvings, so log₂ 8 = 3. Look how slowly this number grows:

Even with a billion elements, thirty halvings are enough to get down to one.

We use base 2 in programming because so many algorithms work by splitting things in two: a sorted range, a tree into left and right subtrees, a problem into two halves. In Big O, though, the base doesn't matter. Changing the base of a logarithm only multiplies it by a constant (log₁₀ n is log₂ n divided by about 3.32), and constants get dropped. That's why it's written as just O(log n).

The classic example is binary search. In a sorted slice, look at the middle element. If the target is larger, ignore the left half. If it's smaller, ignore the right half. Every comparison throws away half of what's left.

Even in the worst case, when the value isn't there, the loop runs about log₂ n times. It only keeps low, high and mid, so the space is O(1).

You can compare it with linear search below. Click a number to search for it with both algorithms at once. Try the last element, which is the worst case for linear search, and then a value that isn't in the array. After that, switch between the sizes: linear search needs twice as many comparisons each time the array doubles, while binary search needs just one more.

You've probably used this strategy without writing any code. In the "guess my number between 1 and 100" game, always guessing the middle finds any number in at most 7 tries, since 2⁷ = 128. Looking up a word in a paper dictionary works the same way: you open it somewhere in the middle and keep discarding half. Even counting the digits of a number is logarithmic. A number with d digits is around 10ᵈ, so it has about log₁₀ n digits.

O(n): linear

In an O(n) algorithm, the cost grows at the same rate as the input. Twice the data, twice the work.

Anything that has to visit every element is linear: adding up a slice, printing it, or searching it when it isn't sorted.

If target is the first element, this returns right away. Since we're being pessimistic, though, we assume the target is at the tail or missing, which means n comparisons. That's exactly the top row of the playground above.

For space, linear means allocating memory in proportion to the input. Building a new slice with a transformed copy of every element is the typical case:

This function is O(n) in time and O(n) in space: it goes through the input once and creates one new element for each element it reads.

O(n log n): linearithmic

O(n log n) usually comes from divide and conquer: split the problem in half, solve each half recursively, then combine the results. Efficient general-purpose sorting algorithms land here.

Merge sort is the easiest one to follow. To sort a slice, split it into two halves, sort each half the same way, and then merge the two sorted halves into one:

The n log n is the product of two separate things, and it's easier to understand them one at a time. Press Sort to watch merge sort split 8 values down to single elements and then merge them back. Count the rows on the way down, and the elements in each merge row on the way up.

• There are O(log n) levels. Every level cuts the slices in half, and 8 can only be halved three times before you're left with single elements, so there are log₂ 8 = 3 levels.
• Each level costs O(n). On the way back up, merge touches every element once per level. The slices get smaller, but there are more of them, so each level still handles all n elements.

log n levels with n work each gives O(n log n). Merge sort also needs O(n) extra space for the merged slices.

Quicksort uses the same divide and conquer idea, but it splits the slice around a chosen element, the pivot, instead of the middle. When the pivots split the data evenly it runs in O(n log n), and in practice it's often faster than merge sort. When the pivot is always the smallest element, as happens with a naive pivot choice on data that's already sorted, the "halves" end up with n − 1 elements and 0 elements. The recursion goes n levels deep and quicksort becomes O(n²). This is the worst-case rule again, and it's why Go's slices.Sort uses pattern-defeating quicksort: it notices when the splits keep going badly and switches to heapsort, which is O(n log n) no matter the input.

O(n²): quadratic

O(n²) is basically a loop inside a loop, both going over the input. For each of the n elements, you do n units of work.

Bubble sort is the usual example. It walks through the slice comparing neighbors and swaps them when they're in the wrong order. After each pass, the largest remaining element has "bubbled up" to the end. It repeats until everything is sorted.

The inner loop gets shorter on every pass, so the exact count is (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons. Expanded, that's n²/2 − n/2. Drop the constant and the smaller term and you're left with O(n²). Space is O(1), because it sorts the slice in place.

Run it below and keep an eye on the counter. Shuffled or reversed, it always makes the same number of comparisons; the input only changes how many swaps happen. Then go from 6 to 12 elements: twice the data, about four times the comparisons.

Quadratic algorithms are fine for small inputs and get painful quickly. A thousand elements means a million comparisons, and a million elements means a trillion. When something was fast in testing and falls over in production, two nested loops over the same data are a good first suspect.

The academic trivia

The classes above cover most everyday code. A few others show up less often but are worth knowing, some because they're surprisingly good and others because they're terrible.

O(√n): square root

O(√n) sits between logarithmic and linear. The best-known example is checking whether a number is prime using trial division:

Divisors come in pairs. If n = a × b, then either a or b is at most √n. So if nothing up to √n divides n, nothing above it will either, and the loop can stop there. For a number around a trillion, that's a million iterations instead of a trillion.

Pick a number and check it. 91 and 221 stop as soon as they hit a divisor, while the primes have to go all the way to √n. With 9973, compare the 98 divisions it needs with the almost ten thousand a naive loop would do.

Notice that here n is the number itself, not the length of a collection. Big O always measures growth against the size of the input, and sometimes that size is a length and sometimes it's a value.

O(2ⁿ): exponential

An O(2ⁿ) algorithm doubles its work every time the input grows by one. This usually comes from a recursive function that calls itself twice and doesn't remember any results, like this naive Fibonacci:

Each call makes two more calls, and the same values get recalculated over and over. fib(50) ends up calling fib(2) billions of times. Listing every subset of a set is exponential too: each element is either in or out, so n elements have 2ⁿ subsets.

Run fib(5) below and follow the calls in the order they happen. Every blue node is a call to a value that was already computed somewhere to its left. Then switch to fib(4) and compare: 9 calls against 15, for an input just one smaller.

This function is also a reminder that recursion uses memory. At any moment there can be up to n calls waiting on the call stack, so the space is O(n) even though the function never creates a slice.

O(n!): factorial

At the far end is O(n!), which shows up when an algorithm tries every possible ordering of its input. Generating all permutations is the direct case:

There are n choices for the first position, n − 1 for the second, and so on, which gives n × (n−1) × … × 1 = n! results. Solving the traveling salesman problem by brute force (try every route, keep the shortest) has the same shape. With 20 cities there are about 2.4 quintillion routes. Checking a billion routes per second, you'd finish in roughly 77 years, so the salesman would retire before the trip was planned.

Generate the orderings of a few letters below. Going from 4 to 5 letters takes you from 24 to 120 results, because every new letter can go in front of every ordering you already had.

Move the slider below to see all the classes side by side. Try n = 30 and watch exponential and factorial take off, then go to a million and see what happens to the quadratic one.

Exponential and factorial algorithms only work for very small inputs. When a problem seems to need one, the real work is usually finding a smarter way to state the problem, or settling for an approximate answer.

Summary

• Big O describes how cost grows with the input. An O(n²) algorithm can beat an O(n) one on small inputs, and Big O tells you which one wins as n grows.
• Analyze the worst case, because it's the only case that's guaranteed.
• Time and space are measured separately. Finding the maximum is O(n) in time and O(1) in space.
• Drop constants and smaller terms: 3n² + 5n + 100 is O(n²).
• Logarithmic means halving. Doubling the input adds one step, and the base of the log doesn't matter.
• n log n usually means divide and conquer: log n levels with O(n) work on each.