Big O Notation: What A-Level CS Actually Expects

Big O notation shows up on every major A-level computer science spec (AQA, OCR, Edexcel) and it trips up a lot of students not because the maths is hard, but because they never see it tied to actual code. This is a practical run-through of what you need to know and how to answer exam questions on it without waffling.

What Big O actually measures

Big O describes how the running time (or memory use) of an algorithm grows as the input size, usually called n, gets larger. It's not a stopwatch measurement in seconds. It's a way of describing growth rate so you can compare algorithms independent of hardware.

When you write O(n), you're saying: if I double the input, the work roughly doubles. O(n²) means doubling the input roughly quadruples the work. That relationship is what examiners want you to identify, not exact operation counts.

The complexities you need cold

For A-level, these are the ones that come up again and again:

• O(1) – constant time. Accessing an array element by index: arr[5]. Doesn't matter how big the array is.
• O(log n) – logarithmic. Binary search on a sorted list. Each step halves the remaining search space.
• O(n) – linear. A single loop through a list, like a linear search checking each item once.
• O(n log n) – linearithmic. Merge sort and quicksort (average case) land here.
• O(n²) – quadratic. Nested loops over the same data, which is exactly what bubble sort, insertion sort, and selection sort do.
• O(2ⁿ) – exponential. Naive recursive Fibonacci without memoisation. Gets ugly fast.

You should be able to look at pseudocode and say which of these it is on sight, because that's mostly what gets tested.

Reading code for complexity

The method that works every time: count the loops and see how they relate to n.

# O(n) - one loop, one pass
for i in range(n):
    print(i)

# O(n^2) - nested loop, both tied to n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - the search space halves each iteration
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

A nested loop where the inner loop's range depends on n is still O(n²), even if it looks slightly different (like for j in range(i) instead of for j in range(n) — that's still quadratic overall, just with a constant factor difference).

Watch out for loops that don't depend on n at all. A loop that always runs 10 times regardless of input size is O(1), even though there's a loop present. Examiners like sneaking this in.

Common sorting algorithms and their Big O

This is a favourite exam topic because it combines two specs at once: sorting algorithms and complexity.

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Merge sort's consistency (same complexity best and worst case) is worth mentioning explicitly if a question asks why you'd pick it over bubble sort for large datasets. Bubble sort's best case of O(n) only applies with an early-exit optimisation when no swaps happen in a pass — mention that detail if you bring it up, since some exam boards expect it.

Where students lose marks

The biggest one: writing