What algorithms does 4.3 cover?

Depth-first and breadth-first graph traversal and the pre-order, in-order and post-order tree traversals; linear search and binary search; bubble sort and merge sort; Dijkstra's shortest path algorithm; and Big-O notation for time and space complexity. You need to trace each algorithm by hand and state and compare their complexities.

When can you use binary search instead of linear search?

Binary search requires the list to be sorted. It examines the middle element and discards the half that cannot contain the target, halving the search space each step, giving O(log n) time. Linear search checks each item in turn, works on any list and is O(n). For large sorted lists binary search is dramatically faster; for small or unsorted data linear search may be simpler.

Why is merge sort more efficient than bubble sort?

Bubble sort uses nested loops, repeatedly swapping adjacent items, so it is O(n squared) and impractical for large lists. Merge sort uses divide and conquer, splitting the list in half recursively and merging sorted halves, which is O(n log n) in all cases. The trade-off is that merge sort is more complex and needs extra memory, while bubble sort is simple and sorts in place.

What does Big-O notation describe?

Big-O describes how the time or memory an algorithm needs grows as the input size n grows, keeping only the dominant term and ignoring constants. Common orders from best to worst are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n squared) quadratic and O(2 to the n) exponential. It measures how an algorithm scales, not its exact run time.

What does Dijkstra's algorithm do?

Dijkstra's algorithm finds the shortest (lowest-cost) path from a start vertex to all other vertices in a weighted graph with non-negative weights. It keeps a tentative distance for each vertex, repeatedly selects the unvisited vertex with the smallest distance using a priority queue, relaxes its neighbours, and marks it visited. It is used for satnav routing and network routing.

EnglandComputer Science

AQA A-Level Computer Science 4.3 Fundamentals of algorithms: traversal, searching, sorting, Dijkstra and Big-O

A deep-dive AQA A-Level Computer Science guide to 4.3 Fundamentals of algorithms. Covers graph and tree traversal, linear and binary search, bubble and merge sort, Dijkstra's shortest path, and Big-O time and space complexity with the common orders of growth.

Generated by Claude Opus 4.818 min read4.3Updated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Jump to a section

What 4.3 actually demands
Traversal
Searching and sorting
Dijkstra's shortest path
Big-O complexity
Check your knowledge

What 4.3 actually demands

Algorithms turn data structures into solutions. AQA expects you to trace each standard algorithm by hand, state its time complexity in Big-O, and compare algorithms to justify a choice. This module pairs directly with 4.2: traversal works on graphs and trees, search and sort on lists, and Dijkstra on weighted graphs.

Traversal

Depth-first traversal explores as far as possible down a branch before backtracking and uses a stack (or recursion); breadth-first traversal explores level by level and uses a queue. For binary trees, pre-order visits the node first, in-order visits it in the middle (giving sorted order in a BST), and post-order visits it last.

Searching and sorting

Linear search checks each item, $O(n)$ , on any list; binary search halves a sorted list each step, $O(\log n)$ . Bubble sort swaps adjacent items, $O(n^2)$ , simple and in place; merge sort splits and merges by divide and conquer, $O(n \log n)$ , faster but using extra memory.

Dijkstra's shortest path

Dijkstra's algorithm finds the lowest-cost path from a start vertex through a weighted graph with non-negative weights, using a priority queue to pick the nearest unvisited vertex, relaxing neighbours and finalising vertices one at a time. It powers satnav and network routing.

Big-O complexity

Big-O expresses how time or memory grows with input size, keeping the dominant term. Learn the order from $O(1)$ to $O(2^n)$ , how to read complexity from loop structure (one loop $O(n)$ , nested loops $O(n^2)$ ), and the difference between tractable and intractable problems.

Check your knowledge

State which data structure depth-first traversal uses and which breadth-first uses. (2 marks)
State the order of nodes for an in-order traversal of a binary tree. (1 mark)
State the requirement binary search has that linear search does not. (1 mark)
Give the worst-case complexity of linear search and binary search. (2 marks)
State the time complexity of bubble sort and merge sort. (2 marks)
Give one advantage of bubble sort over merge sort. (1 mark)
State what Dijkstra's algorithm finds and why it uses a priority queue. (2 marks)
Put $O(n^2)$ , $O(\log n)$ and $O(n)$ in order from most to least efficient. (1 mark)

Sources & how we know this

AQA A-level Computer Science (7517) specification — AQA (2015)