Edexcel 1CP2 · Topic 1 · 1.2h

Computational
Complexity

Time Complexity · Space Complexity · Big O Notation · Algorithm Comparison

CSZoneEdexcel GCSE Computer Science 1CP2

What is Complexity?

Measuring Algorithm Performance

Computational complexity measures how the time or memory requirements of an algorithm grow as the size of the input (n) increases. A more efficient algorithm does the same job with fewer steps.

Time complexity — how the number of steps grows with n

Space complexity — how the memory usage grows with n

Expressed using Big O notation: O(1), O(n), O(n²), O(log n), O(n log n)

Big O Notation

Common Complexity Classes

O(1) — constant time. Always takes the same number of steps regardless of n. e.g. looking up an item by index.

O(log n) — logarithmic. Halves the problem each step. e.g. binary search. Very efficient.

O(n) — linear. Steps increase proportionally with n. e.g. linear search.

O(n log n) — efficient sorts. e.g. merge sort.

O(n²) — quadratic. Very slow for large n. e.g. bubble sort worst case.

Applying Complexity to Algorithms

Comparing Algorithms We Know

Linear search: O(n) — must check every item in the worst case

Binary search: O(log n) — halves search space each step

Merge sort: O(n log n) — divide and conquer with merging

Bubble sort: O(n²) worst case — compares all pairs repeatedly

For 1,000 items: binary search ≈ 10 steps vs linear search ≈ 1,000 steps

Exam Practice

Have a go at this question

Edexcel-style question

Algorithm A has O(n) complexity and Algorithm B has O(n²) complexity. Explain which algorithm would be more efficient when processing a list of 10,000 items.

3 marks

Algorithm A (O(n)) would perform approximately 10,000 operations [1], while Algorithm B (O(n²)) would perform approximately 100,000,000 operations [1]. Algorithm A is far more efficient for large inputs as its execution time grows linearly rather than quadratically [1].

Key Takeaways

What to Remember

Complexity = how algorithm performance scales with input size n

Best to worst: O(1) → O(log n) → O(n) → O(n log n) → O(n²)

Binary search O(log n); Merge sort O(n log n); Bubble sort O(n²)

For large datasets, choose algorithms with lower complexity