3.1.2 Efficiency of Algorithms — AQA 8525

What is Efficiency?

An efficient algorithm solves a problem using as few resources as possible. At GCSE the two key resources are:

Time — how many steps (comparisons, operations) the algorithm performs
Space (memory) — how much RAM the algorithm uses during execution

AQA focuses primarily on time efficiency. You need to compare two algorithms and explain which uses fewer steps.

Why Efficiency Matters

For a list of 1,000,000 items, an inefficient algorithm might need 1,000,000 steps to find an item; an efficient one might need only 20 steps. As datasets grow, efficiency becomes critical.

Comparing Searching Algorithms

Algorithm	Best case	Worst case	Requirement
Linear search	1 comparison	n comparisons	Works on any list
Binary search	1 comparison	log₂(n) comparisons	List must be sorted

For n = 1,000: linear search needs up to 1,000 comparisons; binary search needs at most 10 (log₂(1000) ≈ 10).

For n = 1,000,000: linear search → up to 1,000,000; binary search → at most 20.

Comparing Sorting Algorithms

Algorithm	Comparisons (worst case)	Memory	Complexity
Bubble sort	~n² (e.g. 1,000 items → 1,000,000)	In-place (no extra)	Simple
Merge sort	~n × log₂(n) (e.g. 1,000 items → 10,000)	Extra space needed	More complex

For 1,000 items, merge sort uses approximately 100× fewer comparisons than bubble sort.

Factors Affecting Choice of Algorithm

Factor	Consideration
Input size	Small list → bubble sort is fine. Large list → use merge sort or binary search.
Whether data is sorted	Binary search requires sorted data. Linear search works on any list.
Memory available	Merge sort needs extra memory. Bubble sort is in-place.
Frequency	An algorithm run billions of times needs to be as efficient as possible.

Comparing Two Solutions

Two algorithms can produce the same correct result but differ in how many steps they take.

More Efficient

Fewer steps for same result
Scales better for large data
Better worst-case performance

Less Efficient

More steps for same result
May be simpler to write
Still correct — just slower

Exam tip: Always justify your comparison with numbers or a reason. "Binary search is more efficient because it halves the search space each step, needing only log₂(n) comparisons instead of up to n" scores more marks than "binary search is faster."

⚠️ Common Mistakes

Saying an algorithm is "faster" without explaining why (fewer steps)
Forgetting binary search requires a sorted list
Claiming bubble sort is always bad — it is perfectly fine for small datasets
Confusing time efficiency (steps) with space efficiency (memory)

▶

Video coming soon

This lesson video is in production

Key points covered in this video

Time vs space efficiency
Linear vs binary search — comparisons for n = 1,000,000
Bubble sort vs merge sort — n² vs n log n
Factors influencing algorithm choice
How to write a comparison answer for AQA marks

Click slide or press arrow keys to navigate

✍️

Exam-style Worksheet — 3.1.2 Efficiency of Algorithms

8 AQA-style questions · 22 marks · AI marks your answers and gives feedback

Q1State what is meant by the efficiency of an algorithm.[2 marks]

✅ Mark scheme

Mark scheme

Efficiency is how few resources an algorithm uses to solve a problem [1]; a more efficient algorithm produces the same correct result using fewer steps / less memory [1].

Q2A sorted list contains 1,024 items. How many comparisons does binary search need in the worst case? Show your working.[2 marks]

✅ Mark scheme

Mark scheme

log₂(1024) = 10 [1]; 10 comparisons [1].

Q3Explain why binary search is more efficient than linear search for large sorted lists.[3 marks]

✅ Mark scheme

Mark scheme

Binary search halves the search space each step [1]; it needs only log₂(n) comparisons vs up to n for linear search [1]; e.g. for n=1,000,000: binary needs ~20, linear needs up to 1,000,000 [1].

Q4Give one situation where linear search is preferable to binary search, and explain why.[2 marks]

✅ Mark scheme

Mark scheme

When the list is unsorted [1]; binary search requires sorted data — using it on an unsorted list would give incorrect results [1]. (Also accept: very small list where the overhead of sorting is not justified.)

Q5Approximately how many comparisons would bubble sort vs merge sort need for a list of 1,000 items in the worst case?[3 marks]

✅ Mark scheme

Mark scheme

Bubble sort: ~n² = ~1,000,000 comparisons [1]; merge sort: ~n × log₂(n) = 1,000 × 10 = ~10,000 comparisons [1]; merge sort is ~100× more efficient for this input size [1].

Q6Give two factors (other than number of comparisons) that might influence the choice of algorithm.[4 marks]

✅ Mark scheme

Mark scheme

Memory/space — merge sort needs extra space to merge; bubble sort is in-place [2]; ease of implementation — bubble sort is simpler to code, which matters for small projects or teaching [2]. (1 mark factor + 1 mark explanation, per factor)

Q7Algorithm A sorts a list of 10 items in 100 steps. Algorithm B sorts the same list in 45 steps. Which is more efficient? Justify your answer.[2 marks]

✅ Mark scheme

Mark scheme

Algorithm B is more efficient [1]; it produces the same correct result in fewer steps (45 vs 100) [1].

Q8Explain why efficiency becomes more important as the size of a dataset increases.[4 marks]

✅ Mark scheme

Mark scheme

For small datasets, even inefficient algorithms run fast enough [1]; as data grows, n² algorithms become extremely slow — e.g. 1,000,000² = 10¹² steps [1]; efficient algorithms scale much better — binary search only needs ~20 steps for 1,000,000 items [1]; real-world systems handle millions of records, so efficiency directly affects performance and cost [1].

✓

Compare your answers to the mark schemes above.

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 7

Click to flip

🎉

All cards reviewed!

Term	Definition

🔒

Pro Content

Subscribe to unlock all AQA 8525 lessons, worksheets, quizzes and mini tests.

£7.99/month

or £59/year

Upgrade to Pro

What is Efficiency?

Why Efficiency Matters

Comparing Searching Algorithms

Comparing Sorting Algorithms

Factors Affecting Choice of Algorithm

Comparing Two Solutions

Key points covered in this video

Exam-style Worksheet — 3.1.2 Efficiency of Algorithms

Mini Test — 3.1.2 Efficiency