Algorithmic Complexity & Big-O Notation (OCR A-Level CS 2.3.1)
OCR A-Level CS 2.3.1: time and space complexity, Big-O notation — constant, logarithmic, linear, polynomial and exponential — and comparing algorithms.
Free Complexity Big O revision resources (OCR A-Level Computer Science, 2.3.1)
We’ve made exam-style practice for this exact topic, free to download: Complexity Big O question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
How do you say one algorithm is "faster" than another, regardless of the computer it runs on? You measure how its work grows as the data grows — its complexity — and express it with Big-O notation. Spec point 2.3.1(c)–(d) covers measuring efficiency, the Big-O classes (constant, logarithmic, linear, polynomial, exponential) and comparing algorithms. This is a guaranteed source of Paper 2 marks once you know the shapes.
Time and space complexity
Complexity measures the resources an algorithm uses as the input size (n) grows:
Time complexity — how the number of steps / running time grows with n.
Space complexity — how the memory used grows with n.
We don't measure in seconds (that depends on the hardware). Instead we count how the work scales — because for large n, the rate of growth is what decides which algorithm wins.
Big-O notation
Big-O notation describes the worst-case rate of growth of an algorithm, ignoring constants and lower-order terms. It captures the dominant term: an algorithm doing 3n + 5 steps is O(n), because for large n the n term dominates and constants don't matter.
The classes you must know, best to worst:
O(1) — constant. Time doesn't change with n. E.g. accessing an array element by index.
O(log n) — logarithmic. Time grows very slowly; dividing the problem each step. E.g. binary search.
O(n) — linear. Time grows in proportion to n. E.g. linear search.
O(n²) — polynomial (quadratic). Time grows with the square of n; typically nested loops. E.g. bubble sort, insertion sort.
O(2ⁿ) — exponential. Time doubles with each extra item — quickly becomes impossible. E.g. trying every subset / naïve brute-force.
(OCR groups O(n²), O(n³)… as polynomial, and O(2ⁿ) as exponential.)
Why the differences are dramatic
The classes look similar for tiny inputs but diverge enormously as n grows. For n = 1,000:
Complexity | Operations (≈) |
|---|---|
O(1) | 1 |
O(log n) | 10 |
O(n) | 1,000 |
O(n²) | 1,000,000 |
O(2ⁿ) | astronomically huge |
That's why an O(log n) binary search finds an item in a million-record list in about 20 comparisons, while an O(n) linear search may need a million. The bigger the data, the more the complexity class matters — and the more a better algorithm is worth.
Comparing algorithms
Spec point 2.3.1(d) asks you to compare algorithms by complexity. The rules:
A lower growth class is better for large n: O(log n) beats O(n) beats O(n²) beats O(2ⁿ).
We use the worst case unless told otherwise.
For small n, the constants you ignored can matter, so a "worse" Big-O algorithm can be quicker in practice — Big-O is about scalability.
Consider space complexity too: e.g. merge sort is O(n log n) time but needs extra memory, whereas an in-place sort uses less.
So when comparing bubble sort (O(n²)) with merge sort (O(n log n)), merge sort scales far better for large lists — the standard "outline how bubble sort compares" answer.
Worked example: finding the Big-O of a loop
One loop over n items → O(n) (linear).
A loop nested inside another, each running n times → n × n → O(n²) (polynomial). Spotting "single loop = O(n), nested loops = O(n²)" answers most "state the Big-O" questions.
Common exam mistakes
Keeping constants.
2n + 3is O(n) — drop constants and lower-order terms; keep the dominant term.Mislabelling the classes. O(n²) is polynomial, O(2ⁿ) is exponential — don't swap them.
Forgetting log n is fast. Halving each step (binary search) is O(log n), much better than O(n).
Assuming better Big-O always wins. For small n, constants matter; Big-O describes large-n scalability.
Ignoring space. "Complexity" includes space as well as time — mention memory where relevant.
Quick recap
Complexity = how an algorithm's time or space grows with input size n (not seconds).
Big-O = the worst-case growth rate, keeping the dominant term (drop constants).
Classes, best→worst: O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ) (constant, logarithmic, linear, polynomial, exponential).
Single loop ≈ O(n); nested loops ≈ O(n²); halving each step ≈ O(log n).
Lower growth wins for large n; for small n constants matter, and space counts too.
Frequently asked questions
What is Big-O notation? Big-O notation describes the worst-case rate at which an algorithm's running time or memory use grows as the input size increases. It keeps only the dominant term and ignores constants, so an algorithm taking 3n + 5 steps is described as O(n). It lets you compare algorithms independently of the hardware.
What is the difference between time and space complexity? Time complexity describes how the number of steps or running time of an algorithm grows with the input size, while space complexity describes how the amount of memory it needs grows with the input size. Both are expressed using Big-O notation.
What are the main Big-O complexity classes? From most to least efficient they are: O(1) constant, where time does not change with input size; O(log n) logarithmic, which grows very slowly; O(n) linear, which grows in proportion to n; O(n²) polynomial, typically from nested loops; and O(2ⁿ) exponential, which doubles with each extra item and quickly becomes impractical.
Why does the complexity class matter more for large inputs? For small inputs all algorithms are quick, so the differences are negligible. As the input grows, the rates of growth diverge enormously — for a thousand items an O(n²) algorithm does about a million operations while an O(log n) one does about ten — so the complexity class decides which algorithm is usable for large data.
How do you work out the Big-O of an algorithm? You count how the number of steps grows with the input and keep the dominant term, dropping constants. A single loop over n items is O(n), two nested loops each running n times give O(n²), and repeatedly halving the problem gives O(log n). You normally state the worst case.
Why is binary search O(log n)? Binary search halves the portion of the list still being searched at every step, so the number of items left drops 1000 → 500 → 250 and so on. The number of steps needed is therefore about log₂n, which means even a list of a million items is searched in roughly twenty comparisons.
