This mini-lesson covers AQA 4.3 — Fundamentals of algorithms: the standard algorithms you are expected to trace, code and, crucially, 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 the run time (or memory) of an algorithm grows as the input size n grows. It is about the shape of the growth, not the exact number of steps: constants and lower-order terms are dropped, because for large n they stop mattering.
| 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 |
| O(n²) | polynomial | bubble sort |
| O(2ⁿ) | exponential | brute-force subsets |
| O(n!) | factorial | brute-force travelling salesman |
Read it properly: O(n²) means "grows no faster than n squared" — it 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 extra step.
Linear search inspects each element in turn until it finds the target or runs off the end. It works on any list, sorted or not. Worst case: n comparisons — O(n).
Binary search requires the list to be sorted. It checks the middle item; if the target is smaller it discards the whole upper half, otherwise the lower half. Each comparison halves the search space.
Binary tree search is the same halving idea on a BST: at each node go left if smaller, right if larger. O(log n) on a balanced tree; O(n) if the tree has degenerated into a chain.
The catch: binary search needs sorted data, and sorting costs O(n log n). Sorting once to search many times is a win. Sorting to perform a single search is not.
Bubble sort makes repeated passes, comparing adjacent pairs and swapping them if they are out of order. After pass 1 the largest item has bubbled to the end, so each pass can examine one fewer element.
Merge sort is divide and conquer: split the list in half, recursively sort each half, then merge the two sorted halves by repeatedly taking the smaller of the two front elements.
The honest trade-off: merge sort is far faster on large data but uses extra memory and is harder to code. Bubble sort is trivial to write and needs no extra space, but is unusable beyond a few thousand items. There is no free lunch — you trade time against space.
Both traversals visit every reachable vertex exactly once; both keep a visited set. The only difference is the structure holding the frontier:
| Breadth-first (BFS) | Depth-first (DFS) |
|---|---|
| Uses a queue (FIFO) | Uses a stack (LIFO), or recursion |
| Visits all neighbours, then their neighbours — expanding in rings | Plunges as deep as possible, then backtracks |
| Finds the shortest path in an unweighted graph | Natural for maze solving, topological sort, cycle detection |
| Can use a lot of memory (whole frontier queued) | Memory proportional to the depth |
Both are O(V + E) using an adjacency list.
Exam trap: BFS finds the fewest edges, not the lowest cost. On a weighted graph the fewest-edges route can easily be the most expensive one — that is exactly why Dijkstra exists.
Dijkstra finds the shortest path from one source vertex to every other vertex in a graph with non-negative weights.
Use the predecessor pointers backwards from the destination to reconstruct the route.
Why non-negative weights matter: Dijkstra assumes that once a vertex is finalised no shorter route to it can appear. A negative edge could later reduce that distance, breaking the assumption — so Dijkstra is simply wrong on graphs with negative weights. A* is Dijkstra plus a heuristic estimate of the remaining distance, which steers the search towards the goal and explores far fewer vertices.
| Edge | Weight | Edge | Weight |
|---|---|---|---|
| A – B | 4 | C – D | 8 |
| A – C | 2 | C – E | 10 |
| B – C | 1 | D – E | 2 |
| B – D | 5 | B – E | 12 |
Reverse Polish (postfix) notation puts the operator after its operands: 3 4 + instead of 3 + 4.
Its virtues:
Evaluation: read left to right. Push every operand. On meeting an operator, pop two values, apply the operator (second-popped op first-popped), and push the result.
Link back: the post-order traversal of an expression tree is the reverse Polish form. That is not a coincidence — both put the operator after its operands.
Tap an operation, then tap its order of 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ⁿ) · O(n!) — drop constants and lower terms
Searching: linear O(n), any data · binary O(log n), needs sorted data · BST O(log n) balanced
Sorting: bubble O(n²) time, O(1) space · merge O(n log n) always, O(n) space
Traversal: BFS = queue = fewest edges · DFS = stack = deep then backtrack · both O(V + E)
Dijkstra: relax edges from the closest unvisited vertex; non-negative weights only; A* adds a heuristic
RPN: operator after operands · no brackets or precedence · evaluate with a stack · equals post-order
That is the whole of AQA 4.3. Press Finish to see your score.
You've worked through Fundamentals of algorithms for AQA A-level Computer Science (7517). 🎉
Your stars: 0 / 0
Next: test yourself in the Evaluate stage Confidence Quiz, then lock it in with Verify.