A-level Computer Science Year 12 · Topic 2
Algorithms
Algorithms at A-level is about choosing and analysing efficient methods for searching, sorting and exploring data.
We will compare searches and sorts with big O notation, and add insertion sort and quick sort.
Then we traverse graphs and trees, find shortest paths with Dijkstra and A star, evaluate expressions in reverse Polish notation, and trace algorithms.
- 6 subtopics
- 139 questions
- Free: 2.1 notes and 10 questions
In this topic
- 2.1Searching, sorting and complexityFree below · 24 questions
- 2.2Insertion sort and quick sortOpen in Full Marks · 23 questions
- 2.3Graph and tree traversal: depth-first, breadth-first, pre-order, in-order and post-orderOpen in Full Marks · 25 questions
- 2.4Shortest path algorithms: Dijkstra's algorithm and A*Open in Full Marks · 20 questions
- 2.5Reverse Polish notation and expression evaluation using stacksOpen in Full Marks · 21 questions
- 2.6Representing and tracing algorithms: pseudocode, flowcharts and trace tablesOpen in Full Marks · 26 questions
2.1 · Free notes
Searching, sorting and complexity
Key points
- Linear search is O(n) and works on unsorted data; binary search is O(log n) but requires sorted data.
- Bubble sort and insertion sort are O(n²); merge sort is O(n log n) and uses a divide-and-conquer approach.
- Big O notation describes how run time or space grows with input size, ignoring constants and lower-order terms.
- Common orders from best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
- Choosing an algorithm involves trade-offs between time complexity, space complexity and simplicity of implementation.
In more detail
- Worked binary search: on 1 000 000 sorted items, binary search needs at most 20 comparisons (2²⁰ ≈ 1 048 576); linear search may need 1 000 000.
- Worked merge sort: 8, 3, 5, 1 → 8, 3 | 5, 1 → 3, 8 | 1, 5 → merge → 1, 3, 5, 8.
- Worked complexities: linear search O(n); binary search O(log n); bubble sort O(n²); merge sort O(n log n); accessing an array element O(1).
- Worked growth: for n = 1024, log₂ n = 10, n log₂ n ≈ 10 000 and n² ≈ 1 000 000.
- Worked exponential: checking every subset of 30 items needs 2³⁰ ≈ 10⁹ checks; with 60 items it is about 10¹⁸ — intractable.
Practice
Searching, sorting and complexity: 10 questions
Pick an answer to check it, or open the answer for the explanation.
1. What is the time complexity of binary search?
- O(1)
- O(log n)
- O(n)
- O(n²)
Show answer
B: O(log n). Each step halves the search space.
2. What is the time complexity of merge sort?
- O(n)
- O(log n)
- O(n log n)
- O(n²)
Show answer
C: O(n log n). Splitting gives log n levels, each requiring O(n) merging.
3. What does Big O notation describe?
- The exact run time in seconds
- How run time or space grows with input size
- The number of lines of code
- The memory address used
Show answer
B: How run time or space grows with input size. Constants and lower-order terms are ignored.
4. Which complexity is most efficient for large n?
- O(n²)
- O(n log n)
- O(2ⁿ)
- O(n!)
Show answer
B: O(n log n). O(n log n) grows far more slowly than the others listed.
5. What is the worst-case complexity of bubble sort?
- O(n)
- O(n log n)
- O(n²)
- O(1)
Show answer
C: O(n²). Nested passes over the list give quadratic growth.
6. What is the time complexity of accessing an array element by index?
- O(1)
- O(log n)
- O(n)
- O(n²)
Show answer
A: O(1). The address can be calculated directly.
7. Which sorting algorithm uses a divide-and-conquer approach?
- Bubble sort
- Insertion sort
- Merge sort
- Linear sort
Show answer
C: Merge sort. It splits, sorts and merges sublists.
8. Why is space complexity also important?
- It determines run time only
- Algorithms may need extra memory, which can be limited
- It has no impact
- It only matters for small inputs
Show answer
B: Algorithms may need extra memory, which can be limited. Merge sort, for example, needs extra storage.
9. A teacher must search an unsorted list of 500 names for one name. Which algorithm can be used directly without preparing the data?
- Merge sort
- Linear search
- Binary search
- Interpolation on the sorted list
Show answer
B: Linear search. Linear search checks each item in turn and needs no ordering. Binary search only works if the data is already sorted.
10. A sorted list of 1,000,000 items is searched with binary search. Approximately how many comparisons are needed at most?
- 500,000
- 20
- 1,000
- 1,000,000
Show answer
B: 20. Each comparison halves the search space, so about log₂(1,000,000) ≈ 20 comparisons are needed. 500,000 is the average for linear search.
Keep going in Full Marks
Full Marks has 24 questions on Searching, sorting and complexity (14 more than here), set out in practice levels. You also get notes and 3D models for all 6 subtopics of Algorithms, plus games, timed exams and past papers.