📁 Paper 1 · Topic 1: Computational Thinking
1.2h Computational Complexity & Efficiency
Edexcel 1CP2 · GCSE Computer Science · ~12 min read · 🔒 Pro
Notes
──
Video
──
Slides
──
Worksheet
──
Quiz

What is Computational Complexity?

Computational complexity describes how the time or memory requirements of an algorithm grow as the size of the input (n) increases. It is used to compare the efficiency of different algorithms.

In Edexcel 1CP2, you need to understand and compare the following complexities:

Big-O Notation

Big-O notation describes the worst-case growth rate of an algorithm. The common complexities you need to know are:

ComplexityNameExamplen=10 steps (approx)
O(1)Constant timeAccessing an array by index1
O(log n)Logarithmic timeBinary search3–4
O(n)Linear timeLinear search10
O(n log n)Log-linear timeMerge sort~33
O(n²)Quadratic timeBubble sort (worst case)100

Comparing Algorithms: Search

AlgorithmBest caseWorst caseRequirement
Linear searchO(1) — first item is targetO(n) — target not presentNone
Binary searchO(1) — target is midpointO(log n)Sorted list

Comparing Algorithms: Sort

AlgorithmBest caseWorst case
Bubble sort (basic)O(n²)O(n²)
Bubble sort (optimised)O(n) — already sortedO(n²)
Merge sortO(n log n)O(n log n)

Why Efficiency Matters

For small inputs, the difference between O(n) and O(n²) is negligible. But for large inputs (e.g. n = 1,000,000), an O(n²) algorithm would require 10¹² steps — making it practically unusable — while O(n log n) requires only ~20 million steps.

Exam tip: In Edexcel questions, you may be asked to compare algorithm efficiencies or explain why one algorithm is more suitable than another. Always refer to the complexity class (e.g. O(n) vs O(n²)) and the size of the dataset. Binary search is only more efficient for large sorted lists — for very small or unsorted lists, linear search may be preferred.
⚠️ Common Mistakes
  • Saying binary search is always better — it requires a sorted list and is only better for large lists
  • Saying merge sort always uses less memory — it uses MORE memory than bubble sort
  • Confusing O(log n) and O(n log n)
  • Not referring to n in complexity comparisons — always mention the input size
▶
Video coming soon
In production

Key points

  • Big-O notation explained clearly with real examples
  • O(1), O(log n), O(n), O(n log n), O(n²) compared
  • Why efficiency matters for large datasets
  • Search and sort algorithm comparison
  • Exam technique for complexity questions
Click slide or press arrow keys to navigate
✍️

Worksheet — 1.2h Computational Complexity

8 Edexcel-style questions · AI-marked

Q1State the time complexity of linear search in the worst case.[1]
✅ Mark scheme
O(n) — linear time. [1]
Q2State the time complexity of binary search in the worst case.[1]
✅ Mark scheme
O(log n) — logarithmic time. [1]
Q3Explain what O(n²) means in terms of how an algorithm's performance changes as n grows.[2]
✅ Mark scheme
The number of steps grows proportional to the square of the input size [1]; if n doubles, the number of steps quadruples [1]. (e.g. n=10 → 100 steps; n=100 → 10,000 steps)
Q4State one requirement that must be met before binary search can be used.[1]
✅ Mark scheme
The list must be sorted. [1]
Q5Compare bubble sort and merge sort in terms of time complexity. Which is more efficient for large datasets and why?[3]
✅ Mark scheme
Bubble sort: O(n²) worst case [1]; Merge sort: O(n log n) always [1]; Merge sort is more efficient for large datasets because n log n grows much more slowly than n² as n increases [1].
Q6An algorithm has O(1) complexity. Explain what this means.[2]
✅ Mark scheme
O(1) means constant time [1] — the algorithm takes the same number of steps regardless of the size of the input [1].
Q7A student has a sorted list of 1 million items. Explain why binary search is far more efficient than linear search for this list.[3]
✅ Mark scheme
Linear search is O(n), requiring up to 1,000,000 steps [1]; binary search is O(log n), requiring only about 20 steps (log₂ 1,000,000 ≈ 20) [1]; binary search is therefore approximately 50,000 times faster in the worst case for this list [1].
Q8Place these complexities in order from most to least efficient: O(n²), O(1), O(n log n), O(log n), O(n). Explain your ordering.[3]
✅ Mark scheme
Most efficient first: O(1) → O(log n) → O(n) → O(n log n) → O(n²) [2 for correct ordering]; O(1) is always constant; O(n²) grows the fastest making it least efficient for large n [1].
Topic Quiz
Q 1 of 15
You scored
out of 15
⚡ XP
Click to reveal definition
🎉
Session complete!
TermDefinition
🎯

Mini Test — Complexity & Efficiency

Timed exam-style test. No feedback until submission.

← 1.2g TestingTopic 1Next: 1.2i Arrays & Lists →
🔒

Unlock Pro

Subscribe to access all 59 Edexcel 1CP2 lessons.

£7.99/month
or £59/year
Subscribe →