AQA 7517 · Paper 1 · 4.4.5

Big-O
Notation

Time complexity · Space complexity · Algorithm efficiency · Section 4.4

WHAT YOU'LL LEARN

O(1) · O(log n) · O(n) · O(n log n) · O(n²) · O(2ⁿ) · Comparing algorithms

AQA SPEC LINK

4.4.5 — Time complexity of algorithms

What is Big-O?

Big-O Notation

Big-O notation describes how the time (or space) an algorithm takes grows as input size n increases. It measures the worst-case performance.

We ignore constants and lower-order terms: O(3n + 5) = O(n)

Big-O captures the growth rate, not the exact time

Allows us to compare algorithms independent of hardware speed

Focus on dominant term: O(n² + n) = O(n²)

Complexity Classes

Common Complexity Classes

Notation	Name	Example
O(1)	Constant	Array access by index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search, traversal
O(n log n)	Log-linear	Merge sort, Quick sort (avg)
O(n²)	Quadratic	Bubble sort, Insertion sort
O(2ⁿ)	Exponential	Brute-force TSP, subsets
O(n!)	Factorial	All permutations

O(1) and O(log n)

O(1) — Constant Time

Time does not depend on n at all. Examples: accessing arr[5], hash table lookup (average), push/pop stack.

O(log n) — Logarithmic Time

Time grows very slowly as n increases. Each step halves the problem. Example: binary search on 1,000,000 items needs just 20 comparisons (log₂ 1,000,000 ≈ 20).

O(n) and O(n²)

O(n) — LINEAR

Single loop through all n items. Double n → double time. Example: linear search, printing all items.

O(n²) — QUADRATIC

Nested loops. Double n → quadruple time. Example: bubble sort (n passes × n comparisons).

n=1000: O(n) = 1,000 ops; O(n²) = 1,000,000 ops. Huge difference!

O(2ⁿ)

O(2ⁿ) — Exponential Time

Adding just one more item doubles the time. These are intractable for large n — grow explosively fast.

n	O(n²)	O(2ⁿ)
10	100	1,024
20	400	1,048,576
50	2,500	1.1 × 10¹⁵
100	10,000	1.3 × 10³⁰

Growth Rate Order

Ordering Complexities: Best to Worst

O(1) < O(log n) < O(n) < O(n log n)
< O(n²) < O(n³) < O(2ⁿ) < O(n!)

Algorithms with O(1) to O(n log n) are generally practical. O(n²) becomes slow for large n. O(2ⁿ) and O(n!) are only feasible for very small n.

Worked Examples

Identifying Big-O From Code

FOR i ← 0 TO n-1 → O(n) one loop

FOR i ← 0 TO n-1
 FOR j ← 0 TO n-1 → O(n²) nested loops

WHILE n > 1: n ← n DIV 2 → O(log n) halving

x ← arr[5] → O(1) constant

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) What does Big-O notation measure? [1]
(b) State the time complexity of (i) binary search, (ii) bubble sort. [2]
(c) Two algorithms solve the same problem. Algorithm A is O(n log n); Algorithm B is O(n²). Explain which should be chosen for large datasets and why. [2]
(d) An algorithm has time complexity O(2ⁿ). Why is it described as intractable? [1]

[6 marks]

1 mark

(a) How the time/number of operations grows as input size n increases (worst-case)

2 marks

(b) (i) O(log n) (ii) O(n²)

2 marks

(c) Algorithm A O(n log n) — grows much more slowly than O(n²) for large n; for n=1000: A≈10000 ops vs B=1,000,000 ops

1 mark

(d) Time grows exponentially — adding one item doubles time; becomes impractical even for modest n values

Summary

Key Points to Remember

Big-O = worst-case growth rate of time/space with increasing n

Order (best→worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Ignore constants: O(5n + 3) = O(n); O(2n²) = O(n²)

Intractable = no polynomial solution; O(2ⁿ) or worse

Nested loops → multiply complexities; sequential → add (take dominant)

🎉 Lesson complete — move to the quiz!