OCR A-Level Computer Science: Algorithms — Complete Revision Guide (H446)
OCR A-Level Computer Science: Algorithms — Complete Revision Guide
Algorithms are where computer science stops describing data and starts doing something with it. If the data structures course gave you the nouns, this course gives you the verbs: search, sort, traverse, find the shortest path, recurse, and reason about how the cost of all of these grows as the problem grows. The H446 specification gathers this material chiefly in section 2.3 (algorithms for the main data structures) and 2.2.2 (the thinking abstractly and computational-complexity strand), and the examiners treat it as the most discriminating content in the qualification — it is hard to bluff an algorithm you cannot trace.
This material is examined across both papers, but its centre of gravity is Component 02 (Algorithms and programming), the paper that covers the 2.x sections and rewards candidates who can trace, complete, analyse and compare algorithms on screen and on paper. The standard-algorithm knowledge also feeds Component 01 wherever a systems question turns on efficiency, and it underpins the programming project, where choosing and justifying an appropriate algorithm is exactly the kind of decision the assessment credits. Big O notation, in particular, is the connective tissue of the course: every search, sort and traversal you meet is ultimately filed under its complexity, and the ability to state and justify that complexity is what separates a description from an analysis.
This is Course 6 of 11 on the LearningBro OCR A-Level Computer Science learning path, and it builds directly on the structures from Course 5 — a stack drives depth-first search, a queue drives breadth-first search, and a priority queue drives Dijkstra's algorithm. The course, OCR A-Level CS: Algorithms, moves from the definition of an algorithm through the standard searches and sorts, into graph algorithms and recursion, and finishes with the formal language of efficiency and the sobering question of which problems are tractable at all. By the end you should be able to trace each algorithm step by step, state its best-, average- and worst-case complexity, and justify which algorithm to choose for a given task.
Guide Overview
This course is a ten-lesson sequence that runs from first principles to the limits of computation. Work through them in order — the searches and sorts establish the analysis vocabulary that the later lessons assume.
- Algorithm Basics
- Searching Algorithms
- Bubble Sort and Insertion Sort
- Merge Sort and Quick Sort
- Graph Traversal
- Dijkstra's Algorithm
- A* Algorithm
- Recursion
- Big O Notation
- Optimisation and Tractability
Algorithm Basics: Definitions and Computational Thinking
The Algorithm Basics lesson pins down what an algorithm actually is: a finite, unambiguous, ordered sequence of steps that takes some input and produces some output, and that is guaranteed to terminate. Each of those properties earns marks in a definition question — finiteness and termination distinguish an algorithm from an endless process, and unambiguity distinguishes it from a vague description. This lesson also frames the computational-thinking ideas that the whole course leans on: decomposition (breaking a problem into smaller sub-problems), abstraction (stripping away irrelevant detail to model only what matters), and pattern recognition (spotting that a new problem is an instance of one already solved).
You should be comfortable expressing algorithms in pseudocode and reading them as flowcharts, and — crucially for Component 02 — be able to trace an algorithm using a trace table that records the value of each variable after every step. Tracing is the single most reliable exam skill in this course: a clean trace table demonstrates understanding directly and protects you from the off-by-one errors that lose marks on every other topic. The lesson sets the standard that the rest of the course meets, because every algorithm that follows is something you must be able to trace by hand.
Searching Algorithms: Linear and Binary
The Searching Algorithms lesson contrasts the two searches that anchor the topic. Linear search examines each element in turn from the start until it finds the target or reaches the end; it makes no assumptions about order, works on any list, and runs in O(n) time, with the worst case being a target that is absent or last. Binary search is dramatically faster but carries a precondition: the list must be sorted. It repeatedly inspects the middle element, discards the half that cannot contain the target, and recurses (or iterates) on the half that can, halving the search space each step. That halving gives it O(log n) time — the difference between checking a million items and checking about twenty.
The examiners want both a clean trace and a clear-eyed comparison. Be ready to trace a binary search with explicit low, mid and high pointers, computing mid = (low + high) DIV 2 each pass, and to explain that the precondition is the catch: binary search is only worthwhile if the data is already sorted, or if it will be searched many times to amortise the cost of sorting it once. A frequently set discriminator asks why you might still choose linear search — the answer is an unsorted or frequently changing list, or a list too small for the logarithmic advantage to matter.
Sorting Algorithms: The Quadratic Pair and the Divide-and-Conquer Pair
OCR expects detailed knowledge of four sorts, and the cleanest way to organise them is as two quadratic O(n²) sorts and two divide-and-conquer sorts. The Bubble Sort and Insertion Sort lesson covers the first pair. Bubble sort repeatedly passes through the list, comparing adjacent elements and swapping them if they are out of order, so that the largest unsorted element "bubbles" to its final position each pass; an optimised version stops early if a complete pass makes no swaps, giving a best case of O(n) on already-sorted data. Insertion sort builds the sorted portion one element at a time, taking the next element and inserting it into its correct place among those already sorted, much as you order a hand of playing cards; it too is O(n²) in the worst case but O(n) in the best, and it is efficient on small or nearly-sorted lists.
The Merge Sort and Quick Sort lesson covers the faster pair, both built on divide and conquer. Merge sort recursively splits the list in half until each piece holds a single element, then merges the pieces back together in order; the splitting gives a logarithmic depth and each level does linear work, so its complexity is O(n log n) in all cases, at the cost of needing extra memory for the merge. Quick sort chooses a pivot, partitions the list into elements less than and greater than the pivot, and recurses on each partition; it averages O(n log n) and sorts largely in place, but degrades to O(n²) in the worst case when pivot choices are consistently poor (for example, always picking the first element of an already-sorted list). The table below is the comparison examiners reward.
| Sort | Best case | Average | Worst case | In place? | Notes |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | Yes | Simple; stops early if no swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | Yes | Strong on nearly-sorted data |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | No | Stable cost; needs extra memory |
| Quick sort | O(n log n) | O(n log n) | O(n²) | Yes | Fast in practice; pivot choice matters |
The recurring exam task is to trace one full pass of a named sort over a short list, then to justify a choice of sort for a scenario — small or nearly-sorted data leans to insertion sort, guaranteed performance leans to merge sort, and tight memory with good average performance leans to quick sort.
Graph Traversal: Depth-First and Breadth-First
The Graph Traversal lesson puts the data structures from Course 5 to work. Depth-first search (DFS) explores as far down one branch as possible before backtracking, and is driven by a stack — either an explicit one or the implicit call stack of a recursive implementation. Breadth-first search (BFS) explores all the neighbours at the current distance before moving outward, and is driven by a queue. The single most important consequence, and a reliable exam point, is that BFS finds the shortest path in an unweighted graph because it reaches nodes in order of increasing distance from the source, whereas DFS does not.
Be ready to trace both traversals from a given start node on a small graph, writing down the visit order and the contents of the stack or queue at each step, and to state typical applications: DFS for exhaustive exploration, cycle detection and topological ordering; BFS for shortest-path-in-hops, broadcasting and finding connected components. The clean mental hook is stack equals depth, queue equals breadth — naming the data structure is often worth a mark in itself and demonstrates that you understand why each traversal behaves as it does.
Dijkstra's Algorithm: Shortest Path with Weights
The Dijkstra's Algorithm lesson extends shortest-path finding to weighted graphs, where edges carry non-negative costs and BFS no longer suffices. Dijkstra's algorithm maintains a tentative shortest distance to every vertex, starting at zero for the source and infinity for the rest. It repeatedly selects the unvisited vertex with the smallest tentative distance — efficiently retrieved from a priority queue, which is exactly why you met that structure earlier — marks it visited, and relaxes each of its edges: if the path to a neighbour through the current vertex is shorter than the neighbour's recorded distance, it updates that distance. The algorithm terminates when the destination is visited (or all reachable vertices are processed), having found the shortest distance and, by tracking predecessors, the shortest path itself.
The examiners almost always require a worked trace on a small weighted graph, so you must be fluent with the table that records, for each vertex, its current tentative distance and its predecessor, updated round by round. Two points reliably earn marks: Dijkstra's requires non-negative edge weights (negative weights break the greedy assumption that a visited vertex's distance is final), and the priority queue is what makes the "pick the smallest" step efficient. Trace it slowly, show every relaxation, and reconstruct the path by following predecessors back from the destination.
A* Algorithm: Dijkstra Plus a Heuristic
The A* Algorithm lesson presents the informed search that improves on Dijkstra's by adding a heuristic. Where Dijkstra's considers only the cost so far (call it g), A* prioritises vertices by f = g + h, where h is a heuristic estimate of the remaining cost from that vertex to the goal. A good, admissible heuristic — one that never overestimates the true remaining distance, such as straight-line distance in a map — steers the search toward the goal and so explores far fewer vertices than Dijkstra's, while still guaranteeing the optimal path. In effect, A is Dijkstra's algorithm with a sense of direction*, and Dijkstra's is the special case of A* where the heuristic is always zero.
For the exam, be able to state the f = g + h evaluation function, explain in words what g and h each represent, and describe why an admissible heuristic preserves optimality while pruning the search. You should be able to trace a short example, computing f for each candidate, and to articulate the trade-off: A* is faster on large graphs given a good heuristic, but it depends entirely on having a sensible, admissible estimate, which is not always available. The pairing of Dijkstra's and A* is a favourite "compare and contrast" prompt, so rehearse the relationship explicitly.
Recursion: Algorithms That Call Themselves
The Recursion lesson formalises a technique that has been lurking throughout the course — in binary search, merge sort, quick sort and tree traversal. A recursive subroutine is one that calls itself on a smaller version of the problem, and every correct recursion has two ingredients: one or more base cases that stop the recursion, and a general (recursive) case that moves the problem toward a base case. Omit or mis-state the base case and the recursion never terminates, exhausting the call stack in a stack overflow — which neatly ties the topic back to the stack data structure, because each recursive call pushes a new stack frame holding its parameters, local variables and return address, and each return pops one.
Be ready to trace a recursion such as factorial or Fibonacci by drawing the chain of calls and the values they return, and to convert a simple recursive definition into an iterative one and vice versa. The standard evaluative question asks you to compare recursion with iteration: recursion can express naturally self-similar problems (tree and divide-and-conquer algorithms) far more elegantly and concisely, but it carries the overhead of stack frames and the risk of overflow, whereas iteration is typically more memory-efficient. A strong answer names the call stack explicitly and explains why deep recursion is risky.
Big O Notation: The Language of Efficiency
The Big O Notation lesson gives you the formal vocabulary that every earlier lesson has been pointing toward. Big O describes the asymptotic growth of an algorithm's time or space requirement as a function of input size n — how the cost scales as the problem gets large — while deliberately ignoring constant factors and lower-order terms, because those are dwarfed by the dominant term as n grows. You must know the standard complexity classes and be able to rank them from best to worst, and to assign each algorithm in the course to its class.
| Complexity | Name | Typical example |
|---|---|---|
| O(1) | Constant | Array index access; stack push/pop |
| O(log n) | Logarithmic | Binary search; balanced BST lookup |
| O(n) | Linear | Linear search; single pass over a list |
| O(n log n) | Linearithmic | Merge sort; quick sort (average) |
| O(n²) | Quadratic | Bubble, insertion and selection sort |
| O(2ⁿ) | Exponential | Brute-force subset and many combinatorial searches |
Two skills are examined. The first is deriving the Big O of a fragment of pseudocode by counting how its work depends on n — a single loop is O(n), a nested loop over the same data is O(n²), a halving loop is O(log n). The second is distinguishing best, average and worst case, because the same algorithm can sit in different classes depending on the input (quick sort is O(n log n) on average but O(n²) at worst). You should also be aware of space complexity as the analogous measure for memory. The point examiners reward is the meaning: Big O tells you how an algorithm scales, which is what matters once the data is large, and constant-factor differences are real but secondary.
Optimisation and Tractability: The Limits of Computation
The Optimisation and Tractability lesson is the course's intellectual climax, asking not "how fast is this algorithm?" but "can this problem be solved efficiently at all?" A problem is broadly tractable if an algorithm exists that solves it in polynomial time — O(n), O(n²), O(n³) and so on — and broadly intractable if the only known algorithms run in exponential time, O(2ⁿ) or worse, so that the running time explodes beyond any practical limit even for modest inputs. The classic intractable examples OCR uses are the Travelling Salesman Problem and other combinatorial optimisation problems, where the number of candidate solutions grows so fast that brute force is hopeless for realistic sizes.
The pragmatic response to intractability is the heuristic — a rule-of-thumb method that does not guarantee the optimal answer but finds a good enough answer quickly. You should be able to explain that a heuristic trades guaranteed optimality for tractable running time, and to give an example such as the nearest-neighbour approach to the Travelling Salesman Problem. OCR also expects an outline understanding that some problems are not computable at all — there is no algorithm that solves them on any computer, the Halting Problem being the standard example of an undecidable problem — which marks the absolute limit beyond which more processing power cannot help. The discriminating answer keeps the categories straight: tractable (polynomial), intractable (exponential, attacked with heuristics), and non-computable (no algorithm exists), and uses Big O to make the tractable/intractable boundary precise.
How to Revise Algorithms
Revise algorithms with a pen, not a highlighter. For every algorithm in the course, take a short example and trace it in full with a trace table or a labelled diagram: a binary search with explicit pointers, one pass each of bubble and insertion sort, a complete merge sort recursion tree, a DFS and a BFS from the same start node, and a full Dijkstra's trace on a small weighted graph. Build a master table that lists each algorithm against its best-, average- and worst-case Big O, whether it sorts in place, and one scenario in which you would choose it — these "analyse and justify" questions are dependable marks. Practise deriving Big O from raw pseudocode loops, since that skill transfers to unfamiliar code in the exam, and rehearse the crisp comparisons examiners love: linear versus binary search, the four sorts, DFS versus BFS, Dijkstra's versus A*, and recursion versus iteration. Finally, learn the tractability vocabulary precisely — polynomial means tractable, exponential means intractable, heuristics buy a good-enough answer, and the Halting Problem marks the edge of computability.
When you can trace any of these algorithms cleanly, state and justify its complexity, and argue which algorithm fits a described problem, you have mastered the most discriminating material in H446. Work through every lesson in OCR A-Level CS: Algorithms, and carry the analytical habit forward to the networking and database courses that follow it on the OCR A-Level Computer Science learning path.