What does OCR section 2.3 cover?

Section 2.3 covers the standard algorithms and their analysis: the searching algorithms (linear search, binary search and binary tree search), the sorting algorithms (bubble sort, insertion sort, merge sort and quick sort), graph traversal (breadth-first and depth-first) and binary tree traversal (pre-order, in-order, post-order), the shortest-path algorithms Dijkstra and A*, and Big-O notation with the complexity classes used to judge an algorithm's efficiency and suitability.

Why is binary search faster than linear search?

Binary search halves the remaining items at every comparison because the list is sorted, so it needs about log base 2 of n comparisons, giving O(log n). Linear search checks items one by one and in the worst case examines all n of them, giving O(n). On a million sorted items, binary search needs about 20 comparisons while linear search may need a million, but binary search requires the list to be sorted first.

Why are merge sort and quick sort faster than bubble sort?

Bubble sort and insertion sort are O(n squared) because they make about n passes of n comparisons. Merge sort and quick sort use divide and conquer: they split the list into halves (about log n levels) and do n work per level, giving O(n log n) on average. For large lists the difference between O(n squared) and O(n log n) is enormous, which is why libraries use the divide-and-conquer sorts.

How does A* differ from Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path in a weighted graph by always expanding the nearest unvisited node and relaxing its neighbours' tentative distances. A* adds a heuristic estimate of the remaining distance to the goal and expands the node minimising distance-so-far plus that estimate. This steers the search towards the goal, so A* usually explores fewer nodes and is faster when a good heuristic is available.

How should I revise section 2.3?

Rehearse tracing each algorithm by hand with a trace table, especially binary search, a bubble or insertion sort pass, and a breadth-first traversal, because OCR sets trace questions. Learn each algorithm's Big-O and the order of the complexity classes, and practise determining the Big-O of a code fragment from its loops. Know the data structure each traversal uses and which tree traversal gives sorted output.

EnglandComputer Science

OCR A-Level Computer Science Algorithms and complexity: searching, sorting and Big-O made exam-ready

A deep-dive OCR H446 guide to Component 02 section 2.3, algorithms. Covers the searching algorithms (linear, binary, binary tree) with traces, the sorting algorithms (bubble, insertion, merge, quick), graph and tree traversal with Dijkstra and A*, and Big-O notation with the complexity classes used to compare algorithms.

Generated by Claude Opus 4.815 min readH446 2.3Updated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Jump to a section

What this section actually demands
Searching and sorting
Traversal and analysis
How this section is examined
Check your knowledge

What this section actually demands

Section 2.3 is the algorithms paper's analytical core. OCR rewards two things: accurately tracing an algorithm step by step (trace tables for searches and sorts, a queue or stack for traversals), and reasoning about efficiency with Big-O. You should be able to run each algorithm by hand and state and justify its complexity.

This guide walks through the topics in order and sets out the exam patterns OCR repeats. Each topic has a matching dot-point page with practice; this overview ties them together.

Searching and sorting

Searching algorithms and their complexity covers linear search ( $O(n)$ ), binary search ( $O(\log n)$ , requiring a sorted list) and binary tree search ( $O(\log n)$ balanced, $O(n)$ unbalanced), each with a trace. The recurring skill is tracing a binary search and justifying why halving gives logarithmic time.

Sorting algorithms and their complexity covers bubble and insertion sort ( $O(n^2)$ ) and the divide-and-conquer merge and quick sort ( $O(n \log n)$ , quick sort $O(n^2)$ worst case). The classic questions trace a pass of bubble or insertion sort and explain why merge sort is $O(n \log n)$ .

Traversal and analysis

Graph and tree traversal algorithms covers breadth-first (queue) and depth-first (stack) traversal, the three binary-tree traversals (in-order giving sorted output on a BST), and the shortest-path algorithms Dijkstra and A*, set as "BFS versus DFS" and "Dijkstra versus A*" questions.

Big-O notation and algorithm analysis covers the complexity classes from $O(1)$ to $O(2^n)$ , why constants and lower-order terms are dropped, and determining the Big-O of code (single loop $O(n)$ , nested loops $O(n^2)$ ), used to compare and choose algorithms.

How this section is examined

A typical OCR profile for section 2.3:

Trace tables. Trace a binary search, a sort pass, or a graph traversal step by step.
Complexity statements. Give and justify the Big-O of each standard algorithm.
Comparison. BFS versus DFS (with data structures and uses); Dijkstra versus A*.
Determine Big-O. Read a code fragment's loops and state its time complexity, ordering the classes.

Check your knowledge

A mix of recall and applied questions covering the section. Attempt them under timed conditions, then check against the solutions.

State the precondition for binary search. (1 mark)
State the worst-case time complexity of bubble sort. (1 mark)
State the data structure used by a depth-first traversal. (1 mark)
State which binary tree traversal gives a BST's values in ascending order. (1 mark)
Order $O(1)$ , $O(n)$ , $O(\log n)$ and $O(2^n)$ from most to least efficient. (2 marks)
State the time complexity of an algorithm with two nested loops, each running $n$ times. (1 mark)

Solutions

Six questions covering searching, sorting, traversal, and Big-O complexity.

Step 1: Q1 - State the precondition for binary search

Binary search works by comparing the target to the middle element and discarding half the remaining items at each step. This halving strategy only makes sense if the items are in order; without sorting, there is no way to know which half contains the target.

Final answer: The list must be sorted.

Step 2: Q2 - State the worst-case time complexity of bubble sort

Bubble sort compares adjacent elements and repeatedly passes through the list. In the worst case (a reverse-sorted list), every pass must make approximately $n$ comparisons, and about $n$ passes are needed, giving a total of approximately $n \times n$ operations.

Final answer: $O(n^2)$ .

Step 3: Q3 - State the data structure used by a depth-first traversal

Depth-first traversal follows a path as far as possible before backtracking. A stack (either explicit or via the call stack in a recursive implementation) stores the nodes waiting to be revisited, because the last node added is the first one explored.

Final answer: A stack (or recursion); breadth-first uses a queue.

Step 4: Q4 - State which binary tree traversal gives values in ascending order

The three binary tree traversals visit nodes in different orders relative to visiting the left and right subtrees. For a binary search tree, the left subtree holds smaller values and the right subtree holds larger values, so visiting left, then the current node, then right produces values in ascending order.

Final answer: In-order traversal (left, node, right).

Step 5: Q5 - Order the complexity classes from most to least efficient

Efficiency is measured by how quickly the number of operations grows with $n$ . Constant time $O(1)$ is best because it does not grow at all; logarithmic $O(\log n)$ grows very slowly; linear $O(n)$ grows proportionally; and exponential $O(2^n)$ grows catastrophically fast.

Final answer: $O(1)$ , $O(\log n)$ , $O(n)$ , $O(2^n)$ (constant, then logarithmic, then linear, then exponential).

Step 6: Q6 - State the time complexity of two nested loops each running $n$ times

The outer loop runs $n$ times and the inner loop runs $n$ times for each iteration of the outer loop. The total number of times the inner body executes is therefore approximately $n \times n$ , giving quadratic time.

Final answer: $O(n^2)$ , since the body runs about $n \times n$ times.

Sources & how we know this

OCR AS and A Level Computer Science (H046, H446) specification — OCR (2015)