Mission 1 · Spec 2.3.1
Analysing algorithms: Big O
Measuring time and space complexity, and the Big O notation for constant, logarithmic, linear, polynomial and exponential algorithms.
- Starter 5 min
- Learn 15 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
Double the data
An algorithm takes 1 second for 1,000 items. How long for 2,000 items if it is linear? Quadratic? Logarithmic?
Reveal
Linear: 2 s. Quadratic: 4 s. Logarithmic: barely more than 1 s. Big O describes how time grows as the input grows, ignoring constants.
Key ideas
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search; searching a balanced BST |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort; quick sort (average) |
| O(n²) | Polynomial | Bubble sort; insertion sort; nested loops over the data |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci; brute-forcing all subsets |
Space complexity measures how much memory an algorithm needs, e.g. merge sort needs O(n) extra space; bubble sort sorts in place.
Growth chart
Match the complexity
Exam-style questions
1. State the time complexity of this algorithm and justify your answer.
[2 marks]for i = 0 to n - 1 for j = 0 to n - 1 print(grid[i, j]) next jnext i
Mark scheme
- O(n²) (1)
- The inner loop runs n times for each of the n iterations of the outer loop (1)
2. Explain why an O(2ⁿ) algorithm may be unusable for large inputs even on a fast computer.
[2 marks]Mark scheme
- The time doubles with each extra item of input (1)
- so for even moderate n the number of steps is astronomically large / would take longer than is practical (1)
TUTOR NOTES
- Misconception: Big O gives the exact running time. It describes the growth rate.
Mission 2 · Spec 2.3.1
Searching and sorting
Linear and binary search, and bubble, insertion, merge and quick sort: tracing them and comparing their complexity.
- Starter 5 min
- Learn 15 min
- Lab 25 min
- Quiz 10 min
- Exam 15 min
Pick a pivot
A teacher lines up a class by height by picking one student, sending shorter students to their left and taller to their right, then repeating on each side. Which algorithm is this?
Reveal
Quick sort: the chosen student is the pivot. Each partition puts the pivot in its final place.
Algorithms and complexities
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) |
| Binary search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Quick sort's worst case happens when the pivot is always the smallest or largest item, e.g. choosing the first item of an already-sorted list.
Sort visualiser
Search race
Exam-style questions
1. Write an algorithm for a binary search on an array items for a value target, returning its index or −1.
Mark scheme
- Initialise low = 0 and high = length − 1 (1)
- Loop while low ≤ high (1)
- Calculate mid = (low + high) DIV 2 (1)
- If items[mid] == target, return mid (1)
- Else if items[mid] < target, low = mid + 1, else high = mid − 1 (1)
- Return −1 after the loop (1)
2. Compare merge sort and quick sort.
[4 marks]Mark scheme
- Both are divide-and-conquer, O(n log n) on average (1)
- Merge sort is always O(n log n); quick sort's worst case is O(n²) (1)
- Merge sort needs O(n) extra memory; quick sort sorts in place (1)
- Quick sort is often faster in practice due to less copying (1)
TUTOR NOTES
- Lab prompt: run quick sort several times and count comparisons compared with bubble sort.
- Pivot choice: the lab uses the first item; textbooks vary, so accept any consistent method.
Mission 3 · Spec 2.3.1
Algorithms for data structures
Algorithms for stacks, queues, linked lists and trees, and breadth-first and depth-first traversal of graphs.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Exploring a building
You explore a building to find a friend. Would you check every room on each floor before moving up, or go as far as you can down one corridor first?
Reveal
Floor by floor is breadth-first (uses a queue). One corridor at a time, backtracking at dead ends, is depth-first (uses a stack, or recursion).
Key ideas
Breadth-first traversal
Visit a node, add all its unvisited neighbours to a queue, then take the next node from the front of the queue. Visits nodes level by level; finds the shortest path in an unweighted graph.
Depth-first traversal
Visit a node, then recursively visit each unvisited neighbour, going as deep as possible before backtracking. Uses a stack (or the call stack).
Stacks and queues
Push/pop and enqueue/dequeue must check for full and empty conditions and update the pointers correctly.
Linked lists and trees
Traverse a linked list by following pointers from the start until null. Add to a BST by comparing and moving left or right until an empty position is found.
Breadth-first vs depth-first
Binary search tree
Exam-style questions
1. Write an algorithm to push an item onto a stack stored in an array stack of size 10, using a pointer top (−1 when empty).
Mark scheme
- Check whether the stack is full: top == 9 (1)
- If full, output an error / return False (1)
- Otherwise increment top (1)
- Store the item at stack[top] (1)
2. Describe how a breadth-first traversal of a graph works.
[4 marks]Mark scheme
- Start at the root / chosen node, mark it visited and add it to a queue (1)
- Remove the node at the front of the queue (1)
- Add each of its unvisited neighbours to the queue and mark them visited (1)
- Repeat until the queue is empty (1)
TUTOR NOTES
- Exam habit: name the supporting data structure (queue for BFS, stack for DFS).
Mission 4 · Spec 2.3.1
Shortest path: Dijkstra and A*
Finding the shortest route through a weighted graph with Dijkstra's algorithm, and speeding it up with A* and a heuristic.
- Starter 5 min
- Learn 15 min
- Lab 25 min
- Quiz 10 min
- Exam 15 min
Sat-nav
A sat-nav finds the quickest route across the country in under a second. It can't try every route. How might it avoid wasting time on roads heading the wrong way?
Reveal
It uses an estimate of the remaining distance (a heuristic, e.g. straight-line distance) to prioritise promising roads. That's the idea behind A*.
Key ideas
Dijkstra's algorithm
- Set the start's distance to 0 and all others to infinity.
- Visit the unvisited node with the smallest distance.
- For each neighbour, if distance via this node is smaller, update its distance and previous node.
- Repeat until the destination is visited (or all nodes are).
- Follow the "previous" nodes back from the destination to get the route.
A* algorithm
Like Dijkstra, but chooses the node with the lowest f = g + h: g is the distance so far and h is a heuristic estimate of the distance to the goal. A good heuristic means fewer nodes are visited. For the shortest path to be guaranteed, h must never overestimate.
Shortest path
Compare how many nodes each algorithm visits.Exam-style questions
1. Explain how the A* algorithm differs from Dijkstra's algorithm.
[3 marks]Mark scheme
- A* uses a heuristic estimate of the distance from each node to the goal (1)
- It chooses the next node using f = g + h, rather than just the distance so far (1)
- so it focuses on promising nodes and usually visits fewer nodes / finds the path faster (1)
2. Using the graph in the lab, show how Dijkstra's algorithm finds the shortest path from A to G. Show the distances at each stage.
[6 marks]Mark scheme
- Correct initial distances (A = 0, others infinity) (1)
- Nodes visited in order of smallest distance (1)
- Distances updated correctly when a shorter route is found (2)
- Correct final shortest distance (1)
- Correct route found by following previous nodes (1)
- Use the lab's "Run to the end" to check.
TUTOR NOTES
- Lab prompt: run both algorithms. How many nodes does each visit before finding G?
- Misconception: Dijkstra only finds the route to one node. It finds shortest distances from the start to every node it visits.