How fast is it? Big-O in plain words

Picture a printed phone book: thousands of names in alphabetical order, each with a phone number. Finding one name among 1,000 takes a moment. Now the book has 1,000,000 names. It is a thousand times bigger, so is finding a name a thousand times slower? That depends on how you search. This lesson gives you a way to answer questions like that before you run anything: count the steps, then describe how the count grows.

Measuring speed by counting steps#

Say you want the number for Sana Patel. There are two sensible ways to look.

• Start at the first name and read every name in order until you reach hers.
• Open the book in the middle. If her name comes later in the alphabet, keep the second half; if it comes earlier, keep the first half. Open the half you kept in its middle, and repeat.

With 1,000 names, the first way can take 1,000 looks. The second takes at most 10, because 1,000 halved ten times leaves less than one name. With 1,000,000 names the first way can take 1,000,000 looks, and the second at most 20.

Here are both searches as code. To keep the program small, the book is a row of numbered pages, and we look for the last page, which is the worst place to be for the first method. Each method counts its looks.

Compare the three lines. One by one, the looks go 10, 100, 1000: ten times the pages means ten times the looks. By halving they go 4, 7, 10, so ten times the pages adds only about three looks.

Why not use a stopwatch?

You could time the two methods instead. The trouble is that a stopwatch measures your computer as much as your code. A faster laptop, another program running in the background, or Java speeding up as it runs (the JVM compiles busy code into faster machine code while the program is running) all change the time. The count of looks is the same on every machine, every time.

So programmers measure speed by counting. A step is any small piece of work that takes the same time however big the input is, such as comparing two values or reading one array slot. The size of the input is called n: the number of names in the book, say, or of items in a list. Then the question becomes: as n grows, how does the number of steps grow?

Key idea

Count the steps, then ask how the count grows when n grows. That growth tells you whether code will cope with a million items.

Big-O: a name for the growth#

Big-O notation is a short way to write down how the count grows. Reading every page is O(n), said “big O of n” or “order n”: the work grows in proportion to n, so twice the pages means twice the looks. Halving is O(log n): the work grows with the number of times you can halve n. How a method's running time grows with the size of its input is its time complexity, and Big-O is the usual way to write it down.

Big-O deliberately throws detail away. It ignores the exact number of steps and keeps only the shape of the growth. A method that takes 3n + 2 steps and a method that takes n steps are both O(n), because when n doubles, both roughly double. Big-O answers one question: if the input gets bigger, how much more work is there?

The growth rates you will meet#

Most code falls into one of a handful of growth rates, and each comes with a shape of code you can learn to spot. Here they are from fastest to slowest.

O(1): constant time

The work stays the same however big the input gets. Reading scores[3] is one step whether the array holds 6 numbers or 6 million. Java knows where the array starts and how big each slot is, so it works out where slot 3 lives and goes straight there, the way a room number takes you to room 304 without knocking on the 303 doors before it. Calling get(3) on an ArrayList is O(1) too, because the list keeps its values in an array.

Finding a value when you do not know its position is a different job. Step through this program and compare its two halves.

Reading slot 3 is a single line with no loop. Finding 90 took six looks, one for each slot up to the match, and a longer array would take more. When you know where a value is, reaching it costs O(1); when you have to search for it, you pay for the search.

O(log n): logarithmic time

Here the code cuts the problem in half each time around a loop. The phone book's halving search has this shape, and so does this loop, which counts how many times n can be halved before it reaches 1.

It prints 9, 19 and 29. Going from a thousand items to a million costs only 10 more halvings, and going on to a billion costs 10 more again. Each doubling of n adds just one step. (The underscores in 1_000_000 are only there to make the number easy to read; Java ignores them.)

That is why the halving search through a sorted list, called binary search, is so fast. You will write it yourself in searching and sorting.

O(n): linear time

Here the code makes one pass over the input, doing a fixed amount of work for each item. Reading the phone book page by page is O(n), and so are finding 90 above, adding up an array and finding the largest value in a list. In each of them, doubling the number of items doubles the work.

O(n log n): a loop around a halving job

Do an O(log n) job once for each of n items and you get n × log n steps. A loop over n items with a halving loop inside it has this shape. In practice you meet O(n log n) whenever you sort: Arrays.sort, List.sort and Collections.sort all take O(n log n) time. It grows a little faster than O(n) and far slower than O(n²), which is why sorting even a million items is quick. How a sort manages it is a story for the next lesson.

O(n²): quadratic time

Here the code has a loop inside a loop, and both run over the input. A common case is checking a list for repeats by comparing every pair of values. This version counts its comparisons, and the arrays hold no repeats, so it has to try every pair.

10 values need 45 comparisons; 20 values need 190. Doubling n roughly quadruples the work. The exact count is n * (n - 1) / 2: the first value is compared with the 9 after it, the second with the 8 after it, and so on down to 1, and 9 + 8 + ... + 1 = 45. That is about half of n², and a half makes no difference to the shape, so the method is O(n²).

O(2ⁿ): exponential time

Each step up in n doubles the work, or close to it. The example you already know is the naive Fibonacci method from recursion, where every call makes two more calls. Here it is again with a counter.

Each time n goes up by 2, the number of calls grows about 2.6 times: 9, 25, 67, 177, 465. Keep going and it gets out of hand fast. fib(40) makes over 330 million calls, and fib(50) over 40 billion.

Four of them side by side

This program counts three loop shapes at once, doubling n each time. The first column is n itself, which is also what a single loop over n items counts.

Each time n doubles, the halving count goes up by just one, while the loop in a loop multiplies by 4. The n log n count sits in between: going from 8 items to 16 takes it from 24 to 64, a little under 3 times as many. The table sums up all six shapes.

Feel the difference

Numbers like 256 do not look frightening. The gap opens up as n grows. Drag n in the chart below and watch the curves pull apart, then read the table under it, which turns each count into time by pretending every step takes one microsecond, a millionth of a second.

Slide all the way to n = 1,000,000. O(log n) needs about 20 microseconds, O(n) one second and O(n log n) about 20 seconds. O(n²) needs about 11.6 days. O(2ⁿ) is hopeless long before that: at n = 30 it already takes about 18 minutes, and by n = 80 it takes longer than the universe has existed.

Key idea

For big inputs, the growth rate matters far more than the speed of the computer. O(n²) work on a million items takes days at a microsecond a step; O(n log n) work takes seconds.

Working out the Big-O of code#

You rarely need to count every step. A few rules of thumb get you to the answer.

Drop the constants

A method that walks an array twice, once to find the smallest value and once to find the largest, takes about 2n steps. Big-O calls that O(n). A constant multiplier like the 2 depends on details such as what you count as one step, and it does not change the shape: double n and 2n doubles too. Fixed extra work goes the same way, so 3n + 5 is O(n) and a method that always does 7 steps is O(1).

Keep the biggest term

When a count has several parts, the fastest-growing part wins. n² + n is O(n²): at n = 1,000 the n² part is 1,000,000 and the n part only 1,000, a tenth of one percent of the total. The bigger n gets, the less the smaller parts matter.

Steps one after another add

If a method runs one loop and then another, add their costs. An O(n) loop followed by another O(n) loop is O(n + n), which is O(2n), which is O(n). An O(n) loop followed by an O(n²) loop is O(n + n²), which is O(n²) once you keep the biggest term.

Loops inside loops multiply

A loop that runs n times, with a loop inside that also runs n times, does n × n work: O(n²). If the inner loop halves instead, the total is n × log n. When the two loops run over different things, keep both sizes: a loop over m customers with a loop over n products inside it does m × n work, O(m × n), and calling both sizes n would hide that.

A loop that halves or doubles is logarithmic

If the loop variable is divided by 2, or multiplied by 2, each time around, the loop runs about log n times. Dividing by 3 or by 10 instead is still O(log n). Logs to different bases differ only by a constant multiplier, and constants are dropped.

Now use the rules on three counters at once. Before you run it, decide which counter grows like n, which like log n, and which like n².

a counts one loop: n, so 16. b halves from 16 to 8 to 4 to 2 and stops before 1: log n, so 4. c counts a loop in a loop: n × n, so 256.

Key idea

Drop constants, keep the biggest term, add what runs in sequence, multiply what is nested, and count a halving loop as log n. Those rules give you the Big-O of most code by reading it.

Best, average and worst case#

The same method can take very different numbers of steps on inputs of the same size. Searching a guest list for a name finishes at once if the name is first, and checks every name if it is last or missing.

There are eight guests. Ana is found after 1 comparison: that is the best case, the luckiest input of this size. Hana, at the end, and Zoe, who is not on the list at all, both need all 8: the worst case, the input that makes the method work hardest. If every guest is equally likely to be the one you want, you check about half the list, 4.5 comparisons here: the average case.

So searching an unsorted list is O(1) in the best case and O(n) in the average and worst cases, since n / 2 is still O(n). When someone gives one Big-O for a method without saying which case, they usually mean the worst case, because it is a promise: the method never does worse than that. The big exception is hashing. The famous O(1) of a HashMap is an average, as the next section explains.

What Java's collections cost#

Every collection makes trade-offs, and knowing what each operation costs lets you pick the right one. The Java API documentation states most of these costs in each class's description. These are the ones you will use most.

Amortized: cheap when averaged over many adds

In the ArrayList lesson you watched an ArrayList run out of spare slots and copy every value into an array half as big again. That copy costs O(n), so now and then a single add is slow. But after each copy, many cheap adds follow before the next one, and the bigger the list gets, the longer the gap between copies. Spread over a long run of adds, the cost per add stays constant. Averaging the cost over a whole sequence of operations like this is called amortized cost. The ArrayList documentation puts it in one line: adding n elements requires O(n) time. You will see why the sums work out when you build your own ArrayList.

Average O(1): what a HashMap promises

A HashMap's O(1) depends on its keys' hashCode spreading them out across the buckets, as you saw in HashMap and HashSet. If many keys land in the same bucket, a lookup has to search through that bucket. With well-behaved keys such as String and Integer that does not happen in practice, and get and put stay fast however many entries the map holds.

Making a slow check fast#

Back to the duplicate check from the O(n²) section. Comparing every pair works, but its 190 comparisons for 20 values become about 500 billion for a million values. There are two good ways to do better.

Sort first: O(n log n)

After sorting, equal values end up next to each other, so one pass that compares each value with the one before it finds any repeat. Arrays.sort(sorted) sorts an array in place, and Arrays.copyOf(values, values.length)makes a copy first, so the caller's array keeps its order.

It prints true, then false. Now cost it with the rules. Copying is O(n), sorting is O(n log n), and the pass is O(n). They run one after another, so they add: O(n + n log n + n). Keeping the biggest term leaves O(n log n). For a million values that is roughly 20 million steps instead of 500 billion.

Remember what you have seen: O(n)

A HashSet answers “have I seen this value before?” in O(1) on average. So walk the array once. For each value, ask the set whether it is already there; if it is, you have found a repeat, and if not, add it. That is n rounds of O(1) work: O(n) on average, with no sorting at all.

1import java.util.HashSet;
2 
3public class Main {
4    // Returns true if any value appears more than once.
5    static boolean hasDuplicate(int[] values) {
6        HashSet<Integer> seen = new HashSet<>();
7        // TODO: one loop over values. If seen already contains the value,
8        // return true. Otherwise add the value to seen.
9        return false;
10    }
11 
12    public static void main(String[] args) {
13        System.out.println(hasDuplicate(new int[] {42, 7, 19, 7, 3}));
14        System.out.println(hasDuplicate(new int[] {5, 1, 4, 2}));
15        System.out.println(hasDuplicate(new int[] {8}));
16        System.out.println(hasDuplicate(new int[] {}));
17        System.out.println(hasDuplicate(new int[] {9, 9}));
18    }
19}

For a million values, that is about a million set operations, against roughly 20 million steps for sorting first and 500 billion comparisons for checking every pair.

Key idea

The biggest speed-ups come from changing the algorithm or the data structure. Swapping a pair-by-pair search for a HashSet took this check from O(n²) to O(n).

Space complexity: memory counts too#

Time is one cost of running code, and memory is the other. Space complexity describes how much extra memory a method needs as n grows, written with Big-O in the same way. The input itself is usually left out of the count; what matters is what the method adds.

The duplicate checks make a good comparison. The pair-by-pair version needs two index variables whatever the size of the array: O(1) extra space. The sort-first version copies the array: O(n). The HashSet version may end up storing every value: O(n). The HashSet bought its speed with memory, and trading memory for time like this is one of the most common moves in programming.

Recursion has a memory cost that is easy to miss. Every call that has not returned yet keeps a frame on the call stack, as you saw in recursion. Step through both sums below and watch the call stack.

Both print 10. The loop does its work inside one frame with a few variables, whatever n is: O(1) extra space. The recursive version stacks up a frame for every call, from sumRecursive(4) down to sumRecursive(0), so five frames for n = 4 and n + 1 frames in general: O(n) space. Make n large enough and the stack runs out, which is the StackOverflowError you met in the recursion lesson.

Further reading#

• ArrayList in the Java SE 25 API documentation, whose description lists which operations take constant, amortized constant and linear time
• HashMap in the Java SE 25 API documentation, on what its constant-time promise depends on
• TreeMap in the Java SE 25 API documentation, with its guaranteed log(n) operations
• JEP 180: Handle Frequent HashMap Collisions with Balanced Trees