This mini-lesson covers OCR 2.3 — Algorithms: the standard algorithms you must be able to trace, code and — the part that separates the top grades — compare by complexity.
Work through each screen, answer the questions as you go (some are recall, some are calculations you must actually work out) and collect ⭐ stars. Press Start when you're ready.
Big-O describes how an algorithm's cost grows with the input size n. Constants and lower-order terms are dropped, because for large n they cease to matter.
| Order | Name | Example |
|---|---|---|
| O(1) | constant | array access, hash lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | linear search |
| O(n log n) | linearithmic | merge sort, quicksort (average) |
| O(n²) | polynomial | bubble sort, insertion sort |
| O(2ⁿ) | exponential | brute-force subsets |
Space complexity is measured the same way. Bubble and insertion sort are O(1) space — they sort in place. Merge sort is O(n) space, because merging needs a temporary array. You are always trading time against space.
Read it properly: O(n²) is an upper bound on the worst case. Doubling n makes an O(n²) algorithm take four times as long, but an O(log n) algorithm take just one more step. That is the whole reason complexity is worth studying.
Linear search — check each element in turn. Works on any list, sorted or not. Worst case O(n).
Binary search — requires a sorted list. Check the middle; discard the half that cannot contain the target; repeat. Each comparison halves the search space, so it is O(log n).
Binary tree search — the same halving idea on a BST: go left if smaller, right if larger. O(log n) on a balanced tree — but if the data was inserted already sorted, the tree degenerates into a chain and it collapses to O(n).
The catch: binary search needs sorted data, and sorting costs O(n log n). Sort once and search a million times, and it is a huge win. Sort in order to perform a single search, and you have wasted your time — use linear search.
| Sort | Best | Worst | Space |
|---|---|---|---|
| Bubble | O(n) with a swap flag | O(n²) | O(1) |
| Insertion | O(n) if nearly sorted | O(n²) | O(1) |
| Merge | O(n log n) | O(n log n) | O(n) |
| Quick | O(n log n) | O(n²) | O(log n) |
Bubble — compare adjacent pairs and swap; after each pass the largest item has bubbled to the end. Total comparisons in the worst case = n(n−1)/2.
Insertion — take each item and insert it into its correct place among those already sorted, shuffling the larger ones along. Excellent on nearly sorted data; it is what people actually do with a hand of cards.
Merge — divide and conquer: split in half, sort each half recursively, then merge the sorted halves. There are log₂ n levels, each merging n items, so it is O(n log n) in every case.
Quicksort — choose a pivot, partition the list into items smaller and larger than it, and recurse on each partition. Fast in practice, and sorts nearly in place.
Quicksort's worst case: if the pivot is always the smallest or largest item — which happens if you take the first element of an already sorted list — each partition removes only one element, giving n levels of recursion and O(n²). Choosing a random or median pivot makes that vanishingly unlikely, which is why real implementations do exactly that.
| Breadth-first (BFS) | Depth-first (DFS) |
|---|---|
| Uses a queue (FIFO) | Uses a stack (LIFO), or recursion |
| Visits all neighbours first, expanding in rings | Plunges as deep as possible, then backtracks |
| Finds the shortest path in an unweighted graph | Maze solving, topological sort, cycle detection |
| Memory grows with the whole frontier | Memory proportional to the depth |
Both visit every reachable vertex once, both keep a visited set, and both are O(V + E) with an adjacency list.
The trap: BFS finds the route with the fewest edges, not the lowest cost. On a weighted graph the fewest-edges route can easily be the most expensive one — which is exactly why Dijkstra's algorithm exists.
Dijkstra finds the shortest path from a source to every other vertex in a graph with non-negative weights:
It fails on negative weights, because it finalises each vertex on the assumption that no cheaper route can appear later — an assumption a negative edge destroys.
A* is Dijkstra plus a heuristic. Each vertex is scored:
By expanding the lowest f first, A* is steered towards the goal and explores far fewer vertices than Dijkstra. If the heuristic never overestimates (it is admissible — straight-line distance is the classic choice), A* is guaranteed to find the shortest path.
Set h(n) = 0 and A* becomes Dijkstra exactly. The heuristic is the entire difference: it is informed guidance about which direction is worth exploring, and it is why every satnav uses A*, not Dijkstra.
| Edge | Weight | Edge | Weight |
|---|---|---|---|
| A – B | 3 | C – D | 4 |
| A – C | 6 | C – E | 7 |
| B – C | 2 | D – E | 2 |
| B – D | 9 |
Tap an algorithm or operation, then tap its complexity.
Tap an item on the left, then its partner on the right.
Big-O: O(1) · O(log n) · O(n) · O(n log n) · O(n²) · O(2ⁿ) — measure space as well as time
Searching: linear O(n) on any data · binary O(log n) needs sorted data · BST O(log n) balanced, O(n) degenerate
Sorting: bubble & insertion O(n²) in place · merge O(n log n) always but O(n) space · quicksort O(n log n) average, O(n²) with a bad pivot
Traversal: BFS = queue = fewest edges · DFS = stack = deep then backtrack · both O(V + E)
Path finding: Dijkstra relaxes from the closest unvisited vertex (no negative weights) · A*: f = g + h, admissible h guarantees optimality
That is the whole of OCR 2.3. Press Finish to see your score.
You've worked through Algorithms for OCR A-level Computer Science (H446). 🎉
Your stars: 0 / 0
Next: test yourself in the Verify stage.