Cambridge IGCSE 0478 · Topic 7 · 7.3d

Algorithm
Efficiency

Comparisons · Linear & Binary Search · Bubble Sort & Merge Sort

CSZoneCambridge IGCSE Computer Science 0478

What is Efficiency?

Measuring Algorithm Performance

The efficiency of an algorithm describes how well it performs as the input size n grows. At IGCSE level, efficiency is measured by the maximum number of comparisons needed in the worst case.

A more efficient algorithm needs fewer comparisons — it finishes faster, especially for large datasets

Two types of algorithm to compare: searching algorithms (linear search, binary search) and sorting algorithms (bubble sort, merge sort)

The exam will ask you to compare algorithms by counting comparisons for a given n, or to explain why one is more efficient than another

Searching — Linear Search

Check Every Item in Turn

Linear search starts at the first item and checks each one in order until the target is found or all items have been checked.

Maximum comparisons = n (the target is the last item, or not found at all)

Works on: any list — sorted or unsorted. Simple to implement.

Example: searching a list of 100 items — worst case = 100 comparisons

Inefficient for large datasets — every extra item adds one more potential comparison

Searching — Binary Search

Halve the Search Space Each Time

Binary search compares the target to the middle item. If the target is smaller, discard the upper half; if larger, discard the lower half. Repeat on the remaining half.

Maximum comparisons = log₂(n) — the search space halves with each step

Requires: the list must be sorted first — binary search will not work on an unsorted list

Example: 16 items → max 4 comparisons (16 → 8 → 4 → 2 → 1); 1024 items → max 10 comparisons

Much more efficient than linear search for large sorted datasets

Sorting — Bubble Sort

Repeatedly Swap Adjacent Items

Bubble sort makes repeated passes through the list. On each pass, adjacent items are compared and swapped if they are in the wrong order. Larger values "bubble up" to the end.

Maximum passes = n − 1; total comparisons ≈ n² / 2 (roughly n² for large n)

Example: 8 items → up to 7 passes, ~28 comparisons; 16 items → ~120 comparisons

Simple to understand and code, but very inefficient for large lists — comparisons grow quadratically

An optimisation: if a complete pass makes no swaps, the list is already sorted — stop early

Sorting — Merge Sort

Divide, Sort, Merge

Merge sort uses a divide and conquer approach: split the list in half repeatedly until each sub-list has one item (already sorted), then merge the sub-lists back together in order.

Maximum comparisons ≈ n × log₂(n) — far fewer than bubble sort for large n

Example: 8 items → ~24 comparisons (vs ~28 for bubble); 1000 items → ~10,000 (vs ~500,000 for bubble)

More complex to implement than bubble sort, but significantly more efficient for large datasets

Does not require the list to be sorted first — it creates a sorted output from an unsorted input

Efficiency Comparison

All Four Algorithms Side by Side

Algorithm	Type	Max comparisons	Sorted required?
Linear search	Searching	n	No
Binary search	Searching	log₂(n)	Yes
Bubble sort	Sorting	~n²/2	No
Merge sort	Sorting	n × log₂(n)	No

n items	Linear	Binary	Bubble	Merge
8	8	3	28	~24
16	16	4	120	~64
1,024	1,024	10	~524,288	~10,240

Exam Practice

Have a go at this question

Cambridge IGCSE 0478 style

A list contains 16 items. State the maximum number of comparisons needed by (i) a linear search and (ii) a binary search to find an item. Explain why binary search is more efficient than linear search.

4 marks

(i) Linear search: maximum 16 comparisons [1]. (ii) Binary search: maximum 4 comparisons (log₂ 16 = 4) [1]. Explanation: binary search halves the search space with each comparison [1], so the number of comparisons grows much more slowly — logarithmically rather than linearly [1]. (Note: binary search requires the list to be sorted first.)

Key Takeaways

What to Remember

Linear search: max n comparisons, works on any list. Binary search: max log₂(n), requires sorted list

Bubble sort: max ~n²/2 comparisons, simple but slow for large n

Merge sort: max n × log₂(n) comparisons — much faster than bubble sort for large datasets

For n=16: linear=16, binary=4, bubble=120, merge≈64. Binary search and merge sort win at scale