AQA 8525 · Section 3.1 · 3.1.2

Efficiency of
Algorithms

Time Complexity · Comparing Algorithms · Best & Worst Case

CSZoneAQA GCSE Computer Science 8525

Learning Objectives

By the end of this lesson you will be able to...

Explain what is meant by the efficiency of an algorithm

Compare algorithms in terms of the number of comparisons or operations needed

Describe best case and worst case performance for searching and sorting algorithms

Choose the more efficient algorithm for a given situation

What is Efficiency?

Why Efficiency Matters

An algorithm is efficient if it solves a problem using the fewest operations (comparisons, steps) possible. A more efficient algorithm takes less time and uses less memory, especially with large data sets.

WITH 10 ITEMS

Linear search: up to 10 comparisons
Binary search: up to 4 comparisons
Difference: small

WITH 1,000,000 ITEMS

Linear search: up to 1,000,000 comparisons
Binary search: up to 20 comparisons
Difference: massive!

Comparing Algorithms

Search Algorithm Comparison

Feature	Linear Search	Binary Search
Requires sorted list?	No	Yes
Best case	1 comparison (first item)	1 comparison (middle item)
Worst case (n items)	n comparisons	log₂(n) comparisons
For 1024 items (worst)	1024 comparisons	10 comparisons
Efficiency	Lower	Much higher

Key:Binary search halves the list each time — so it needs roughly log₂(n) steps for n items.

Sorting Comparison

Bubble Sort vs Merge Sort

Feature	Bubble Sort	Merge Sort
Approach	Compare adjacent pairs, swap	Divide and conquer
Best case (sorted list)	n-1 comparisons	n log₂(n) comparisons
Worst case (reversed)	n² comparisons	n log₂(n) comparisons
For 8 items (worst)	~56 comparisons	~24 comparisons
Suitable for	Small lists	Large lists

Note:Merge sort is always more efficient for large datasets. Bubble sort is simpler to code but much slower.

Exam Practice

Have a go at this question

AQA-style question

A list contains 64 items. Explain why binary search would be more efficient than linear search for finding an item in this list. Use numbers in your answer.

3 marks

MARK SCHEME

Linear search: up to 64 comparisons in the worst case [1]. Binary search: up to 6 comparisons (log₂64=6) [1]. Binary search halves the remaining list each time so needs far fewer steps [1].

Key Takeaways

What to Remember

Efficiency = fewer operations = faster for larger datasets

Binary search: log₂(n) steps worst case (requires sorted list)

Linear search: n steps worst case (works on any list)

Merge sort is more efficient than bubble sort for large lists; bubble sort is simpler for small ones