OCR J277 requires you to compare the searching and sorting algorithms covered in the specification. You need to know their time complexity, space requirements, and when each is most suitable.
Search Algorithms — Linear vs Binary
Property
Linear Search
Binary Search
Time complexity
O(n)
O(log n)
Sorted list required?
No
Yes — must be sorted
Best case
O(1) — target at index 0
O(1) — target is midpoint
Worst case
O(n) — n comparisons
O(log n) — log₂n comparisons
Suitable for large data?
No — slow
Yes — very efficient
Memory usage
O(1)
O(1)
Works on unsorted data?
Yes
No
Best use case
Small/unsorted lists
Large sorted lists
Sort Algorithms — Bubble, Merge, Insertion
Property
Bubble Sort
Merge Sort
Insertion Sort
Worst case
O(n²)
O(n log n)
O(n²)
Best case
O(n) optimised
O(n log n)
O(n)
Average case
O(n²)
O(n log n)
O(n²)
In-place?
Yes
No — O(n) extra
Yes
Stable?
Yes
Yes
Yes
Ease of implementation
Simple
Complex (recursive)
Simple
Good for large data?
No
Yes
No
Good for nearly sorted?
OK (optimised)
No benefit
Very good
Good for small data?
Yes
No benefit
Yes
Time Complexity — At a Glance
n (items)
O(n) — linear
O(log n) — binary
O(n log n) — merge
O(n²) — bubble/insertion
10
10
3
33
100
100
100
7
664
10,000
1,000
1,000
10
9,966
1,000,000
1,000,000
1,000,000
20
20,000,000
1,000,000,000,000
Which Algorithm to Choose? — Scenarios
Scenario 1: Search a sorted list of 1 million records
Binary search — O(log n) ≈ 20 comparisons vs 1,000,000 for linear search
Scenario 2: Search a small unsorted list of 10 items
Linear search — no need to sort first, list is small enough
Scenario 3: Sort 1,000,000 customer records for a database
Merge sort — O(n log n) vastly outperforms O(n²) at this scale
Scenario 4: Sort a small list of 10 items in a simple program
Bubble or insertion sort — simple to implement, negligible difference at n=10
Scenario 5: Sort a nearly-sorted list where memory is limited
Insertion sort — near O(n) for nearly sorted data, in-place (no extra memory)
Scenario 6: Sort a list, but memory is extremely limited
Bubble or insertion sort — both are in-place. Merge sort requires extra O(n) memory
Exam tip: When asked to "compare" or "evaluate" algorithms, consider: time complexity (best AND worst case), whether a sorted list is needed, memory usage (in-place or not), and suitability for the scenario. Don't just name the complexity — explain what it means. E.g. "binary search is O(log n), meaning for 1 million items it only needs about 20 comparisons." Always justify your recommendation in context.
⚠️ Common Mistakes
Saying binary search works on unsorted data — it does NOT
Saying merge sort is in-place — it is NOT (requires extra memory)
Claiming one algorithm is "always best" — context matters
Forgetting that O(n log n) is better than O(n²) — even though n log n "has n in it", it grows much slower
Not mentioning the sorted list requirement when comparing linear and binary search
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.1.3d Algorithm Comparison
8 questions · 20 marks
Q1State the time complexity of: (a) bubble sort worst case (b) merge sort (c) binary search (d) linear search[4]
Q2A student needs to search a sorted list of 500,000 records. Which search algorithm should they use and why?[2]
✅ Mark scheme
Binary search [1] — it is O(log n), requiring approximately 19 comparisons vs 500,000 for linear search. The list is sorted, so binary search's pre-requirement is met [1].
Q3Explain why merge sort is preferred over bubble sort for sorting a large dataset.[3]
✅ Mark scheme
Merge sort is O(n log n) [1] while bubble sort is O(n²) [1]. For large n, O(n log n) is much more efficient — e.g. for 1 million items: ~20 million vs ~1 trillion operations [1].
Q4Give one advantage of bubble sort over merge sort.[1]
✅ Mark scheme
Any one: bubble sort is in-place (no extra memory required) [1]; simpler to implement [1]; O(n) best case with the swap flag optimisation (vs O(n log n) for merge sort) [1].
Q5A system has very limited memory and needs to sort a small list. Which sort algorithm should be used and why?[2]
✅ Mark scheme
Bubble sort or insertion sort [1] — both are in-place, requiring no extra memory beyond a small variable. Merge sort requires O(n) extra memory which would be unsuitable [1].
Q6Compare insertion sort and bubble sort. Give one similarity and two differences.[3]
✅ Mark scheme
Similarity (1): both O(n²) worst case / both in-place / both simple [1]. Differences (any 2): insertion sort shifts elements, bubble sort swaps adjacent pairs [1]; insertion sort is O(n) best case for sorted data, bubble sort O(n) only with swap flag [1]; insertion sort works better for nearly-sorted data [1].
Q7Explain what "in-place" means and state which of the four OCR J277 algorithms are in-place.[3]
✅ Mark scheme
In-place means the algorithm sorts/operates within the original data structure without creating a copy [1]. In-place: bubble sort, insertion sort [1]. NOT in-place: merge sort [1].
Q8For n = 1,000,000 items, calculate (approximately) the maximum number of operations for: (a) binary search (b) linear search[2]
Q3You need to search an unsorted list. Which algorithm must you use?
Q4For 1,000,000 items, approximately how many comparisons does binary search need?
Q5Which algorithm is best for sorting a large dataset?
Section B — Short Answer [5 marks]
Q6Compare linear search and binary search. In your answer include: time complexity, when each should be used.
Mark schemeLinear search: O(n) — use when list is unsorted or small [1]. Binary search: O(log n) — much faster for large lists, but requires sorted list [1]. Award 1 mark per valid comparative point (max 2).
Q7Explain why merge sort is preferred over bubble sort for large datasets.
Mark schemeMerge sort is O(n log n) vs O(n²) for bubble sort [1]. At large n, this is dramatically faster — e.g. 1 million items: ~20 million operations (merge) vs ~1 trillion (bubble) [1].
Q8Give a scenario where bubble sort would be preferred over merge sort.
Mark schemeAny valid scenario: when the list is small (overhead of merge sort not worth it) [1]; when memory is very limited (bubble sort is in-place; merge sort needs O(n) extra) [1]; when the list may be already sorted (bubble sort can exit early O(n)) [1].
Q9Which algorithms have O(n²) worst-case complexity? State them all.
Mark schemeBubble sort and insertion sort [1] — both have O(n²) worst case. Merge sort is O(n log n), binary search is O(log n), linear search is O(n) [1].
Q10A student says "we should always use binary search because it's faster." Evaluate this statement.
Mark schemeNot always — binary search requires the list to be sorted first [1]. If the list is unsorted and only needs searching once, linear search is preferable because sorting first would add overhead [1]. Also, for very small lists, linear search is simpler with negligible speed difference [1].