The big idea: Big O describes how an algorithm's work grows as the data grows.
It is not how long it takes in seconds — that depends on the machine. It is the shape of the growth, which does not.
The four complexities, with the steps each needs at 10, 100 and 1,000 items. Step through them.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
O(1) and O(log n)
- O(1) constant — the same work whatever the size
- Reading an array by position; push and pop on a stack
- O(log n) logarithmic — doubling the data adds one step
- Binary search, because each step discards half
O(n)
- Linear — twice the data, twice the work
- Linear search, or adding up every value
- One loop over the data
- Perfectly acceptable for most purposes
O(n²)
- Quadratic — twice the data, four times the work
- Bubble sort and selection sort
- A loop inside another loop
- This is what stops working as data grows
How to work it out: Count the loops over the data.
No loop is O(1). One loop is O(n). A loop inside a loop is O(n²). Halving the data each step is O(log n).
Constants are dropped: Two separate loops over the same data is 2n steps — but Big O calls that O(n), not O(2n).
Big O is about the shape of the growth, and a constant multiplier does not change the shape.
Stop wasting time on topics you know
Our AI identifies your weak areas and focuses your study time where it matters. No more overstudying easy topics.
Time complexity
- How the number of steps grows
- What people usually mean by Big O
- Bubble sort: O(n²) time
- Binary search: O(log n) time
Space complexity
- How the extra memory grows
- Not counting the input itself
- Bubble sort: O(1) space — it sorts in place
- An algorithm that copies the whole list: O(n) space
The two can be traded: Storing results you have already worked out saves time and costs memory.
Recomputing them each time saves memory and costs time. A question asking you to choose is usually asking which of the two is scarce.
Why n² stops working
Why log n is so good
Small data hides everything
How this is tested — you must derive the complexity from the loops, and say what it means at scale. It comes up two ways:
Paper 2 — working with code
- Describe or calculate an algorithm's Big O, 3-5 marks
- Compare two algorithms' scalability
- Choose one for a stated amount of data
Paper 2 — the algorithmic-thinking question
- The no-code question often asks for reasoning about growth
- Explain why one algorithm stops being usable
The classic trap: Treating Big O as a measure of speed. An O(n²) algorithm can beat an O(n log n) one on small data. Big O says how the work grows, which is what matters as data scales.
Give the time complexity of this, explain how you worked it out, and say what happens if the list grows from 1,000 to 10,000 items.
for i in range(len(items)):
for j in range(len(items)):
if items[i] == items[j] and i != j:
print("Duplicate")
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
Give the time complexity of this, explain how you worked it out, and say what happens if the list grows from 1,000 to 10,000 items.
for (int i = 0; i < items.length; i++) {
for (int j = 0; j < items.length; j++) {
if (items[i] == items[j] && i != j) {
System.out.println("Duplicate");
}
}
}
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.