Big O notation explained

What Big O notation measures, what each of the common orders does when the data doubles, and what the notation throws away. Programs in your browser count the comparisons a linear search, a binary search, a bubble sort and a merge sort really make as the list grows, and chart them.

Guidefree, runs in your browser

Big O notation says how the work an algorithm does grows when the job gets bigger. It does not say how many seconds the algorithm takes, and it is not interested in how fast your computer is. It answers one question: if the list gets twice as long, what happens to the work?

On this page a robot's program counts the comparisons that a linear search, a binary search and a bubble sort really make, on lists that get longer and longer, and charts them. Each demo below is a real program you can change and run.

The idea in one line

O(the shape of the growth)

Write down how many steps the algorithm takes for a job of size n, throw away everything that does not grow fastest, throw away any number in front of it, and put what is left inside O( ). That is the algorithm's order, or its time complexity.

Counting operations instead of seconds

Seconds are a bad measure of an algorithm. They depend on the machine, on the language, on what else the machine is doing, and on the day. Run the same program on a laptop and on the robot and you get two different answers, neither of which tells you anything about the algorithm.

So count the operations instead. For a search or a sort, the operation worth counting is the comparison: one moment when the program asks "is this the one?" or "is this one bigger than that one?". Count those, and you have a number that is the same on every machine, for ever.

The demos below count comparisons by adding 1 to a counter on the line that does the comparing, which is exactly what your program would do to measure itself.

O(n) and O(log n): the two searches

The first demo searches for a reading that is not in the list, which makes both searches do their worst. It does that on a jumbled list of 10 readings, then 20, then 40, up to 200, and plots how many comparisons each search made.

from bugbot import *
connect()

# change the sizes and press Run
SIZES = [10, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200]
TARGET = -1        # a reading that is not there: the worst case

def readings(n):
    # the same jumbled list every time: 0 to n - 1, shuffled
    items = list(range(n))
    seed = 7
    for i in range(n - 1, 0, -1):
        seed = (seed * 1103515245 + 12345) % 2147483648
        j = seed % (i + 1)
        items[i], items[j] = items[j], items[i]
    return items

def linear_search(items, target):
    checks = 0
    for x in items:
        checks = checks + 1              # one comparison
        if x == target:
            return checks
    return checks

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    checks = 0
    while low <= high:
        mid = (low + high) // 2
        checks = checks + 1              # one comparison
        if items[mid] == target:
            return checks
        elif target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return checks

for n in SIZES:
    jumbled = readings(n)
    ordered = sorted(jumbled)
    a = linear_search(jumbled, TARGET)
    b = binary_search(ordered, TARGET)
    plot("linear", a)
    plot("binary", b)
    print("n =", n, "| linear", a, "| binary", b)
    wait(0.2)

Each point on the chart is one list size, the smallest on the left and 200 on the right. The robot does not move: the work is all in the program.

Linear search looks at every reading, so it makes exactly n comparisons. Double the list and you double the work. That is O(n).

Binary search throws away half of what is left after every comparison, so the number it needs goes up by 1 each time the list doubles: 3 for 10 readings, 7 for 200, and about 20 for a million. That is O(log n), and on a chart beside a straight line it looks almost flat. The chart gives it a scale of its own on the right, because on linear search's scale its line would lie along the bottom.

O(1) is the third shape, and it does not need a demo: items[0] reads the first item of a list of a million as quickly as it reads the first item of a list of three. Nothing is searched, so nothing grows.

O(n²) and O(n log n): two sorts

Now the same lists, sorted instead of searched. Bubble sort compares each pair of neighbours and swaps them if they are the wrong way round, again and again until the list is in order. Merge sort splits the list in half, sorts each half the same way, and then merges the two sorted halves by comparing their fronts.

from bugbot import *
connect()

# change the sizes and press Run
SIZES = [10, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200]

def readings(n):
    # the same jumbled list every time: 0 to n - 1, shuffled
    items = list(range(n))
    seed = 7
    for i in range(n - 1, 0, -1):
        seed = (seed * 1103515245 + 12345) % 2147483648
        j = seed % (i + 1)
        items[i], items[j] = items[j], items[i]
    return items

def bubble_sort(items):
    a = list(items)
    checks = 0
    for end in range(len(a) - 1, 0, -1):
        for i in range(end):
            checks = checks + 1          # one comparison
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
    return checks

merge_checks = 0

def merge_sort(a):
    global merge_checks
    if len(a) <= 1:
        return a
    middle = len(a) // 2
    left = merge_sort(a[:middle])
    right = merge_sort(a[middle:])
    out = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        merge_checks = merge_checks + 1  # one comparison
        if left[i] <= right[j]:
            out.append(left[i])
            i = i + 1
        else:
            out.append(right[j])
            j = j + 1
    return out + left[i:] + right[j:]

for n in SIZES:
    jumbled = readings(n)
    a = bubble_sort(jumbled)
    merge_checks = 0
    merge_sort(jumbled)
    plot("bubble", a)
    plot("merge", merge_checks)
    print("n =", n, "| bubble", a, "| merge", merge_checks)
    wait(0.2)

Bubble sort compares every reading with every other reading, which is n × (n - 1) ÷ 2 comparisons: 45 for 10 readings, 19,900 for 200. Twenty times the readings, 442 times the work. That is O(n²), and the line on the chart bends upwards and keeps bending.

Merge sort splits the list about log₂ n times, and each level of the split costs about n comparisons to merge, so its total is about n log₂ n: 22 for 10 readings, 1,287 for 200. That is O(n log n), and for 200 readings it does one fifteenth of bubble sort's work. Merge sort has its own scale on the right of the chart again, for the same reason as before.

The doubling test

Here is the quickest way to see an order for yourself. Run the algorithm on a list of n, then on a list of 2n, and divide the second count by the first. The answer is the same for every size, and it is different for every order.

from bugbot import *
connect()

# change the sizes and press Run
SIZES = [8, 16, 32, 64, 128, 256, 512]
TARGET = -1

def readings(n):
    items = list(range(n))
    seed = 7
    for i in range(n - 1, 0, -1):
        seed = (seed * 1103515245 + 12345) % 2147483648
        j = seed % (i + 1)
        items[i], items[j] = items[j], items[i]
    return items

def linear_search(items, target):
    checks = 0
    for x in items:
        checks = checks + 1
        if x == target:
            return checks
    return checks

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    checks = 0
    while low <= high:
        mid = (low + high) // 2
        checks = checks + 1
        if items[mid] == target:
            return checks
        elif target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return checks

def bubble_sort(items):
    a = list(items)
    checks = 0
    for end in range(len(a) - 1, 0, -1):
        for i in range(end):
            checks = checks + 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
    return checks

merge_checks = 0

def merge_sort(a):
    global merge_checks
    if len(a) <= 1:
        return a
    middle = len(a) // 2
    left = merge_sort(a[:middle])
    right = merge_sort(a[middle:])
    out = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        merge_checks = merge_checks + 1
        if left[i] <= right[j]:
            out.append(left[i])
            i = i + 1
        else:
            out.append(right[j])
            j = j + 1
    return out + left[i:] + right[j:]

def counts(n):
    jumbled = readings(n)
    global merge_checks
    merge_checks = 0
    merge_sort(jumbled)
    return {"first item": 1,
            "binary": binary_search(sorted(jumbled), TARGET),
            "linear": linear_search(jumbled, TARGET),
            "merge": merge_checks,
            "bubble": bubble_sort(jumbled)}

before = counts(SIZES[0])
for n in SIZES[1:]:
    now = counts(n)
    for name in ["binary", "merge", "bubble"]:
        plot(name, now[name] / before[name])
    print("n =", n, end=" ")
    for name in before:
        print("| " + name, round(now[name] / before[name], 2), end=" ")
    print("")
    before = now
    wait(0.3)

The three lines settle quickly, and where they settle is the order:

Bubble sort's multiplier is 4.29 at the first doubling and 4.01 at the last. It is heading for exactly 4, and the small extra is the - n ÷ 2 that Big O threw away. This is the whole idea in one number: the bits that were thrown away matter less and less as the job gets bigger.

What the notation throws away, and when it bites

Big O throws away every constant. O(n) and O(100n) are the same order, and so are n² ÷ 2 and 5n². That is what makes it useful: it is a fact about the algorithm rather than about the machine, and nobody has to agree on what one "step" is before they can compare two algorithms.

It also means Big O is silent about small jobs. An O(n²) algorithm with a small constant can beat an O(n log n) algorithm with a big one, right up to the size where the shapes take over.

The demo below counts every operation this time, not only the comparisons: each comparison, each swap in the bubble sort, and each reading moved into the new list in the merge sort. Merge sort does a lot of moving, and on short lists that moving costs more than bubble sort's swapping.

from bugbot import *
connect()

# change the sizes and press Run
SIZES = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]

def readings(n):
    items = list(range(n))
    seed = 7
    for i in range(n - 1, 0, -1):
        seed = (seed * 1103515245 + 12345) % 2147483648
        j = seed % (i + 1)
        items[i], items[j] = items[j], items[i]
    return items

def bubble_ops(items):
    a = list(items)
    ops = 0
    for end in range(len(a) - 1, 0, -1):
        for i in range(end):
            ops = ops + 1                # one comparison
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                ops = ops + 1            # one swap
    return ops

merge_ops = 0

def merge_sort(a):
    global merge_ops
    if len(a) <= 1:
        return a
    middle = len(a) // 2
    left = merge_sort(a[:middle])
    right = merge_sort(a[middle:])
    out = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        merge_ops = merge_ops + 1        # one comparison
        if left[i] <= right[j]:
            out.append(left[i])
            i = i + 1
        else:
            out.append(right[j])
            j = j + 1
        merge_ops = merge_ops + 1        # one reading moved
    while i < len(left):
        out.append(left[i])
        i = i + 1
        merge_ops = merge_ops + 1
    while j < len(right):
        out.append(right[j])
        j = j + 1
        merge_ops = merge_ops + 1
    return out

for n in SIZES:
    jumbled = readings(n)
    a = bubble_ops(jumbled)
    merge_ops = 0
    merge_sort(jumbled)
    plot("bubble", a)
    plot("merge", merge_ops)
    print("n =", n, "| bubble", a, "| merge", merge_ops)
    wait(0.2)

The two lines cross at 8 readings. Below that the O(n²) sort is the cheaper one, and Big O cannot tell you so, because it threw away exactly the numbers that decide it. This is not a curiosity: the sorting code built into real languages usually switches to a simple O(n²) sort for short pieces of the list, for this reason.

So use Big O to choose between algorithms for a job that will get big, and measure the real thing when the job is small or when two algorithms have the same order.

Best, average and worst case

One algorithm can have three different orders, depending on the data it is given.

Unless a question says otherwise, Big O means the worst case. It is the promise you can make about the algorithm: it will never be worse than this. The demos on this page all search for a reading that is not there, so they all measure the worst case.

How to read the order off a program

You can usually see the order without counting anything.

• Statements one after another: add up their orders, then keep the biggest one. O(n) followed by O(n²) is O(n²).
• One loop over n items: n times whatever the body costs. A simple body makes it O(n).
• A loop inside a loop, both over n items: O(n²). Three deep is O(n³).
• A loop that halves what is left each time: O(log n).
• Splitting into halves and doing O(n) work to put them back: O(n log n).
• A function that calls itself twice on a problem one smaller: the calls double at every level, so O(2ⁿ).

Anything with no loop at all over the data is O(1).

Where this is taught

• Comparing algorithms counts the operations an algorithm makes as a function of n, before any notation is put on it.
• Big O notation is the full lesson: dominant terms, the orders, space complexity, and reading an order off code.
• Linear and binary search and the linear and binary search guide count the comparisons of both searches with the robot's camera.
• Bubble sort and insertion sort and Merge sort are the two sorts on this page.
• What an algorithm is and Merge sort and comparing algorithms are the GCSE way in.

Questions

What is Big O notation in simple terms?

It is a way of saying how the work an algorithm does grows as the job gets bigger, with all the detail that stops mattering thrown away. O(n) means that doubling the amount of data doubles the work. O(n²) means doubling it multiplies the work by four. O(1) means the size makes no difference at all.

What does the O in Big O stand for?

Order. O(n²) is read "order n squared", and it means the algorithm's running time grows in the same shape as n².

How do you work out the Big O of an algorithm?

Count the steps it takes for a job of size n, as a formula. Keep only the term that grows fastest, and drop any number multiplying it. So 3n² + 5n + 20 becomes O(n²), and 4n + 100 becomes O(n). With code in front of you it is quicker to count loops: one loop over the data is O(n), a loop inside a loop is O(n²), and a loop that halves the data each time is O(log n).

What is the difference between O(n) and O(n²)?

O(n) grows in step with the data: twice the data, twice the work. O(n²) grows with the square: twice the data, four times the work. On the demo above, twenty times the readings gave twenty times the work for linear search and 442 times the work for bubble sort.

Why is binary search O(log n)?

Because each comparison throws away half of what is left. The number of halvings it takes to get from n items down to one is log₂ n, so the comparisons go up by one each time the list doubles. The demo shows 3 comparisons for 10 readings and 7 for 200. A list of a million would take about 20.

Which is better, O(n) or O(log n)?

O(log n), for any list worth the name. O(n) grows in step with the data and O(log n) barely grows at all. For a million items that is a million comparisons against about 20.

What does O(1) mean?

The work never changes, whatever the size of the job. Reading items[5], pushing an item onto a stack and looking a key up in a hash table are all O(1). It does not mean fast, it means the same: an O(1) operation that takes a second still takes a second on a list of a million.

Is O(n log n) good?

Yes. It is the best that a sort can do when it works by comparing pairs of items, and it is close enough to O(n) that in practice it feels the same. Merge sort, quick sort and heap sort are all O(n log n) on average.

What is thrown away in Big O, and does it matter?

Constants and everything except the fastest-growing term. It matters for small jobs, where a constant can decide the winner. The demo above counts every operation of both sorts and finds that bubble sort does less work than merge sort up to 7 readings. It stops mattering as the job grows, which is why the notation keeps what it keeps.

What is the difference between time complexity and space complexity?

Time complexity counts operations; space complexity counts the extra memory the algorithm needs beyond the data itself. Bubble sort sorts inside the list it was given, so its space complexity is O(1). Merge sort builds new lists as it merges, so it needs O(n) extra space. A faster algorithm often pays for its speed in memory.

Is Big O notation on the A level Computer Science specification?

Yes, on all three of the main boards, and not on GCSE. AQA's A level (7517) asks you to be familiar with Big O for constant, logarithmic, linear, polynomial and exponential time and to derive an algorithm's complexity (4.4.4.3). OCR's H446 covers Big O and the comparison of algorithms in 2.3.1. Eduqas asks you to use it to compare efficiency (1.3). At GCSE you compare algorithms in words instead, without the notation.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. A5.2 Big O notation Algorithms and complexity, A level
2. A5.1 Comparing algorithms Algorithms and complexity, A level
3. A5.3 Linear and binary search Algorithms and complexity, A level
4. A5.4 Bubble sort and insertion sort Algorithms and complexity, A level
5. A5.5 Merge sort Algorithms and complexity, A level
6. F5.1 What an algorithm is Algorithms, GCSE
7. F5.9 Merge sort and comparing algorithms Algorithms, GCSE