AQA A-Level Computer Science: Algorithms — Complete Revision Guide (7517)
AQA A-Level Computer Science: Algorithms — Complete Revision Guide
Algorithms are where data structures come alive. Having learned in the data structures course how to store information, this course is about what to do with it — how to search it, sort it, traverse it and find the cheapest route through it, and how to reason rigorously about which method is fastest as the data grows. AQA places the standard algorithms in specification section 4.3 and the analysis of complexity, including Big-O notation, in section 4.4.4. The two sit together for a reason: an algorithm is only half the story until you can say how it scales, and the examiners reward candidates who pair a correct trace with a justified complexity class.
These topics are assessed across all three components. Paper 1, the on-screen exam (2 hours 30 minutes, 100 marks, 40% of the A-Level), focuses on implementation and analysis through code — writing a sorting or searching routine, tracing it for a given input, modifying it, and analysing its Big-O complexity. Paper 2, the written exam (also 2 hours 30 minutes, 100 marks, 40%), focuses on describing and tracing algorithms on paper — stepping through Dijkstra's algorithm on a weighted graph, comparing two sorts, or stating a complexity with justification. The Non-Exam Assessment (NEA), the 75-mark programming project (20%), is where these algorithms become tools: choosing an efficient search or sort, or implementing a traversal, and justifying it, is exactly the kind of decision that evidences a strong solution. Throughout, precise vocabulary — "time complexity", "worst case", "divide and conquer", "heuristic" — earns marks, because examiners reward accurate technical language.
This is one of the core courses on the LearningBro AQA A-Level Computer Science learning path. The course, AQA A-Level CS: Algorithms, works through ten lessons in a deliberate order — beginning with the language of complexity, moving through searching, sorting and the two graph traversals, up to shortest-path and the broader strategies of divide-and-conquer and heuristic optimisation. By the end you should be able to trace each algorithm by hand, state its complexity in all relevant cases, compare algorithms for a given task, and explain the design strategy each one embodies.
Guide Overview
This course is a ten-lesson sequence that builds from the analysis of complexity through searching, sorting and traversal to the highest-level algorithmic strategies. Work through the lessons in order, because the complexity language of the first lesson underpins every comparison that follows.
- Algorithm Complexity and Big-O Notation
- Linear Search and Binary Search
- Bubble Sort, Insertion Sort and Selection Sort
- Merge Sort and Quick Sort
- Graph Traversal: Breadth-First Search
- Graph Traversal: Depth-First Search
- Dijkstra's Shortest Path Algorithm
- A* Search Algorithm
- Divide-and-Conquer Strategies
- Optimisation and Heuristics
Algorithm Complexity and Big-O Notation
The Algorithm Complexity and Big-O Notation lesson gives you the language for every comparison in the rest of the course, so investing here repays itself many times over. Big-O notation describes the upper bound of an algorithm's time (or space) complexity as the input size n grows. Crucially, it abstracts away constant factors and lower-order terms to focus on how performance scales: an algorithm that takes 3n + 7 steps is O(n), because for large n the constant and the multiplier are irrelevant to the growth rate. You must be able to derive the complexity of a code fragment from its structure — a single loop over n items is O(n); two nested loops each over n items is O(n²); halving the problem each step is O(log n).
You should know, and be able to rank, the common complexity classes:
| Notation | Name | Behaviour | Example |
|---|---|---|---|
| O(1) | Constant | Independent of input size | Indexing an array element |
| O(log n) | Logarithmic | Problem halved each step | Binary search |
| O(n) | Linear | Scales directly with input | Linear search |
| O(n log n) | Linearithmic | Efficient comparison sorts | Merge sort |
| O(n²) | Quadratic | Nested iteration | Bubble sort |
| O(2ⁿ) | Exponential | Doubles with each added input | Brute-force combinatorial search |
AQA also expects you to distinguish time complexity from space complexity (the extra memory an algorithm needs), and to reason about best, average and worst case — a single algorithm can have different complexities in each, which is the heart of comparing the sorts later. The examinable habit is to justify an algorithm choice by citing its complexity class, not merely to recite the table. The common pitfall is treating constant factors as significant (Big-O deliberately ignores them) or quoting only the average case when the worst case is what makes an algorithm risky.
Linear Search and Binary Search
The Linear Search and Binary Search lesson covers the two fundamental ways to find an item, and the trade-off between them is a reliable exam staple. Linear search checks each element in sequence until the target is found or the end is reached. Its great virtue is generality: it works on both sorted and unsorted data and on any linear structure. Its cost is speed — its worst-case and average-case time complexity is O(n), because for a large unsorted list you may have to inspect every element.
Binary search is dramatically faster but carries a precondition: the data must be sorted. It repeatedly examines the middle element and discards half the remaining search space — if the target is smaller than the middle, search the left half; if larger, the right half — until the target is found or the space is empty. Because the search space halves each step, its time complexity is O(log n), which is transformative on large data sets: a million-element list needs about twenty comparisons rather than up to a million. You should be able to trace binary search on a sorted array, tracking the low, high and mid pointers at each step, and to implement it both iteratively and recursively (the recursive form linking back to the recursion you met in the programming course).
The exam discriminator is the trade-off: binary search is far faster, but only on sorted data, and keeping data sorted has its own cost, so for a small or frequently-changing unsorted list linear search can be the pragmatic choice. The common pitfall is forgetting the sorted precondition for binary search, or mishandling the mid-point and pointer updates so the search loops forever or skips the target.
Bubble Sort, Insertion Sort and Selection Sort
The Bubble Sort, Insertion Sort and Selection Sort lesson covers the three simple, comparison-based sorts that share an O(n²) worst case but differ in their behaviour and in the lessons they teach.
Bubble sort repeatedly passes through the list, comparing adjacent elements and swapping any that are out of order; after each pass the largest unsorted element "bubbles" to its correct place at the end. With an early-exit optimisation (stop when a pass makes no swaps) its best case on already-sorted data is O(n), but its average and worst case are O(n²). Insertion sort builds a sorted region one element at a time, taking the next element and inserting it into its correct position among those already sorted — the way many people sort a hand of cards. It too is O(n²) in the worst case but O(n) on nearly-sorted data, and it is efficient for small lists and for data that is already mostly in order. Selection sort repeatedly finds the smallest remaining element and swaps it into the next position; it is O(n²) in all cases, but it makes the fewest swaps, which matters when a swap is expensive.
| Algorithm | Best | Average | Worst | Space | Note |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Simple; early exit if no swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Strong on nearly-sorted data |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Fewest swaps |
All three sort in place, using O(1) extra space, which is their shared advantage over the divide-and-conquer sorts. The examinable skill is to trace each by hand, writing the list state after each pass, and to explain why the complexity is quadratic (a pass over n items, repeated up to n times). The common pitfall is muddling the three mechanisms — bubble compares neighbours, insertion grows a sorted prefix, selection hunts the minimum — so rehearse each on the same short list until the distinction is automatic.
Merge Sort and Quick Sort
The Merge Sort and Quick Sort lesson covers the two efficient divide-and-conquer sorts that beat the simple sorts on large data, and contrasting them is among the most heavily examined algorithm comparisons.
Merge sort splits the list into two halves, recursively sorts each half, then merges the two sorted halves by repeatedly taking the smaller of the two front elements. Because the splitting produces about log n levels and each level does O(n) work to merge, its time complexity is O(n log n) in all cases — best, average and worst — which is its great strength: it is consistently efficient and stable (it preserves the relative order of equal elements). Its weakness is space: it needs O(n) extra memory for the temporary sublists during merging.
Quick sort chooses a pivot, partitions the list so that elements smaller than the pivot are on one side and larger on the other, then recursively sorts each partition. Its average-case complexity is O(n log n), and in practice it is often faster than merge sort because of low constant factors and good cache behaviour. But its worst case is O(n²), which occurs when the pivot is repeatedly the smallest or largest element (for example, a poorly chosen pivot on already-sorted data), reducing the partitioning to one element at a time. It typically uses only O(log n) extra space for the recursion stack and is usually implemented in place.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
The examinable judgement is the recommendation in context: merge sort when you need a guaranteed O(n log n) and stability and can afford the memory; quick sort when average-case speed and low memory matter and the O(n²) worst case is unlikely or mitigated by good pivot selection. The common pitfall is asserting "quick sort is the fastest" without the O(n²) worst-case caveat, or confusing which sort needs the extra memory — name the trade-off explicitly.
Graph Traversal: Breadth-First Search
The Breadth-First Search lesson is the first of two ways to systematically visit every vertex of a graph, and it puts the queue from the data structures course to work. Breadth-first search (BFS) explores the graph in layers: it visits all the neighbours of the start vertex first, then all their unvisited neighbours, and so on outward, so vertices are visited in order of increasing distance from the source.
The mechanism is precise and worth memorising as a procedure: start at the source, mark it visited and enqueue it; then repeatedly dequeue the front vertex, visit each of its unvisited neighbours, mark them visited and enqueue them; stop when the queue is empty. The queue is essential — it is what makes the search proceed level by level rather than plunging down one branch. You should be able to trace BFS on a given graph, writing the queue contents and the visit order at each step. The headline application AQA expects you to state is that BFS finds the shortest path (fewest edges) in an unweighted graph, precisely because it reaches vertices in distance order; it is also used in network broadcasting and finding connected components. The common pitfall is forgetting to mark vertices as visited when they are enqueued, which can enqueue the same vertex twice and corrupt the traversal.
Graph Traversal: Depth-First Search
The Depth-First Search lesson covers the complementary traversal, which puts the stack to work — or, equivalently, recursion, which uses the call stack implicitly. Depth-first search (DFS) explores as far along a branch as possible before backtracking: from the current vertex it dives into an unvisited neighbour, then a neighbour of that, and so on, retreating only when it reaches a vertex with no unvisited neighbours.
The mechanism mirrors BFS but swaps the structure: start at the source, mark it visited and push it onto a stack; then look at the top of the stack, visit an unvisited neighbour (mark and push it), and if the top vertex has no unvisited neighbours, pop it; stop when the stack is empty. The recursive form is often cleaner — visit a vertex, then recursively DFS each unvisited neighbour — and is a natural exam example of recursion. You should be able to trace DFS on a graph, recording the stack and the visit order. The applications AQA expects are exploring all paths (such as solving a maze), cycle detection, and topological ordering of a directed acyclic graph; DFS also typically uses less memory than BFS on deep, narrow graphs. The crucial comparison — set this out whenever asked — is that DFS uses a stack and goes deep, while BFS uses a queue and goes wide, and BFS (not DFS) guarantees the shortest path in an unweighted graph. The common pitfall is failing to mark vertices visited, causing infinite loops on cyclic graphs.
Dijkstra's Shortest Path Algorithm
The Dijkstra's Shortest Path Algorithm lesson moves from "fewest edges" to "lowest total weight". Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights — the classic model for a road or rail network where edges carry distances or costs.
The procedure is worth knowing as a reliable, mark-bearing trace. Assign a tentative distance of zero to the source and infinity to every other vertex, and mark all vertices unvisited. Then repeat: select the unvisited vertex with the smallest tentative distance as the current vertex; for each of its unvisited neighbours, calculate the distance to that neighbour through the current vertex, and if it is smaller than the neighbour's recorded distance, update it (and record the current vertex as the way to reach it); mark the current vertex visited so it is never reconsidered. Continue until all vertices are visited or the target is reached. AQA frequently asks you to trace Dijkstra on a given graph, maintaining a table of tentative distances and previous vertices, updating it at each step — and marks are awarded for the working, the systematic process, not just the final number, so show every update.
The efficient implementation uses a priority queue to pick the smallest-distance vertex quickly, giving a complexity of O((V + E) log V) for V vertices and E edges, against O(V²) for a simple array-based version. The crucial precondition to state is that edge weights must be non-negative — Dijkstra can give wrong answers if negative weights are present, because a vertex it has already finalised might be reachable more cheaply via a later negative edge. The common pitfall is omitting that caveat, or selecting the next current vertex by visit order rather than by smallest tentative distance.
A* Search Algorithm
The A* Search Algorithm lesson extends Dijkstra's approach to find a shortest path to a single goal more efficiently by adding informed guidance. Where Dijkstra explores outward purely by distance from the source, A* also uses a heuristic — an estimate of the remaining distance from a vertex to the goal — to steer the search towards the target and avoid exploring directions that lead away from it.
The defining idea is the evaluation function f(n) = g(n) + h(n): at each step A* expands the vertex that minimises the sum of g(n), the actual cost from the source so far, and h(n), the heuristic estimate of the cost remaining to the goal. A common heuristic for a grid or map is the straight-line (Euclidean) or Manhattan distance to the target. Because the heuristic focuses effort towards the goal, A* typically examines far fewer vertices than Dijkstra for a single-target search, which is why it is the workhorse of route-planning and game pathfinding. You should be able to explain the role of the heuristic and to note that its quality matters: a good heuristic that never overestimates the true remaining cost guides A* efficiently to the genuine shortest path, whereas a heuristic of zero reduces A* back to Dijkstra's algorithm. The examinable comparison is exactly that relationship — A* is Dijkstra plus a goal-directed heuristic — and the trade-off that A* needs a sensible heuristic and a known target, where Dijkstra finds shortest paths to all vertices without one. The common pitfall is describing A* as simply "faster Dijkstra" without explaining that the speed comes from the heuristic and applies to single-target search.
Divide-and-Conquer Strategies
The Divide-and-Conquer Strategies lesson lifts the view from individual algorithms to the general strategy that several of them share, which AQA expects you to recognise as a named approach. Divide and conquer solves a problem by three steps: divide the problem into smaller subproblems of the same kind, conquer each subproblem by solving it recursively (until it is small enough to solve directly — the base case), and combine the subsolutions into a solution to the original problem.
You should be able to identify the strategy in the algorithms you already know. Binary search divides the search space in half and recurses on one half. Merge sort divides the list in two, sorts each half recursively, and combines them by merging. Quick sort partitions around a pivot and recurses on each side. The strategy's power is that breaking a problem into halves typically introduces a logarithmic factor, which is why divide-and-conquer algorithms so often achieve O(log n) or O(n log n) where a naive approach would be O(n) or O(n²). The link to recursion is direct: divide-and-conquer is naturally expressed recursively, with the base case stopping the division and the combine step running as the recursion unwinds — the same call-stack behaviour you met in the programming course. The examinable skill is to articulate the three-step structure and to classify a given algorithm as divide-and-conquer (or not). The common pitfall is forgetting the combine step — for some algorithms it is trivial (binary search simply returns the result of the chosen half) but for merge sort the merge is the algorithm's real work, and a good answer says so.
Optimisation and Heuristics
The Optimisation and Heuristics lesson closes the course by confronting the problems that are simply too hard to solve exactly, and the pragmatic strategies for them. An optimisation problem asks for the best solution from many possibilities — the shortest tour, the most valuable packing, the lowest-cost schedule. For some such problems no efficient (polynomial-time) exact algorithm is known; the classic example is the travelling salesman problem, where the only known way to guarantee the optimum is to consider an exponential number of routes, which is intractable for large inputs.
When an exact optimum is computationally infeasible, a heuristic offers a way forward: a rule of thumb or educated strategy that finds a good enough solution quickly, without guaranteeing it is the absolute best. A heuristic trades optimality for tractability — a "nearest neighbour" rule for the travelling salesman, for instance, repeatedly visits the closest unvisited city and usually produces a reasonable, if not optimal, tour in a fraction of the time. This connects directly to the A* heuristic you met earlier and, more broadly, to the theory-of-computation idea of tractable versus intractable problems: tractable problems have polynomial-time solutions and are practically solvable even for large inputs, while intractable problems have only exponential or worse known solutions and force you towards heuristics and approximations. The examinable understanding is why heuristics exist — they are the practical response to intractability — and the honest acknowledgement that they sacrifice the guarantee of optimality for usable speed. The common pitfall is treating a heuristic as if it always finds the best answer; a strong answer states explicitly that it does not, and explains the trade-off.
How to Revise Algorithms
Revise algorithms by tracing them, not by reading about them. For each search and sort, take a short list and write its state after every pass or comparison, then state the best, average and worst-case complexity and why. For the two graph traversals, draw a graph and write out the queue (for BFS) or stack (for DFS) and the visit order step by step, then state in one sentence how they differ and that BFS finds the unweighted shortest path. For Dijkstra, rehearse the distance-table trace until it is mechanical, always noting the non-negative-weights precondition; for A*, be able to write f = g + h and explain the heuristic's role. Build a one-page table of every algorithm against its complexity, the data structure it relies on, and its design strategy (divide-and-conquer, greedy, heuristic), because the "compare, justify and recommend" questions are where the marks concentrate.
When you can trace any of these algorithms by hand, state its complexity in every relevant case with justification, recommend the right algorithm for a described task, and explain the strategy each one embodies, you have the analytical core that both written papers and the NEA reward most heavily. Work through every lesson in AQA A-Level CS: Algorithms, then consolidate it against the rest of the AQA A-Level Computer Science learning path, where these algorithms tie the programming and data structures you have built into complete exam coverage.
Next Steps
Turn analysis into fluency. Open AQA A-Level CS: Algorithms and work through the ten lessons in order, tracing each search, sort and traversal by hand and stating its complexity as you go, then continue along the AQA A-Level Computer Science learning path to consolidate algorithms with the programming and data structures topics they depend on — the combination that the two written papers and the NEA assess together.