A-level · Algorithms

Algorithmic complexity and Big O

Free worked examples, independent practice and self-check answers.

Measuring scalability

Big O describes how a resource requirement grows with input size, usually considering worst-case growth for a stated algorithm. It does not give exact elapsed seconds.

Complexity	Example
O(1)	Reading an array item by index
O(log n)	Binary search in a sorted array
O(n)	Linear search
O(n log n)	Efficient comparison sorts such as merge sort
O(n²)	Simple nested-loop pair comparisons

Analyse this code

def count_matches(a):
    matches = 0
    for x in a:
        for y in a:
            if x == y:
                matches += 1
    return matches

For n values, how many comparisons occur? Identify the time complexity and discuss the space complexity excluding the input.

Think about how an algorithm scales

For each algorithm, decide which operations grow as the input size n increases. Linear search can examine n values in the worst case, whereas binary search repeatedly halves a sorted search space. Merge sort takes O(n log n) time for standard implementations. Describe assumptions when comparing algorithms.

Complexity: a stronger way to practise

Rather than memorising only a list of Big O classes, explain what an input-size increase does to the amount of work. Distinguish worst-case from average-case behaviour when appropriate, and consider why implementation details or small inputs can make observed timings differ from asymptotic models.

Write a simple linear search and count comparisons for a list of length n. Then explain why repeatedly halving an ordered search region yields logarithmic comparisons. Use this reasoning when comparing algorithms in exam questions.

Try without notes: Why might O(n log n) merge sort be preferable to O(n²) bubble sort for large random lists?

Check an example answer and feedback

Its growth rate is generally slower as input size increases, so it usually requires fewer operations for sufficiently large inputs, although memory use and implementation factors also matter.

See OCR A-level revision and AQA A-level revision.