Fundamentals of Algorithms
What's covered
Key facts
For 1,024 sorted items the worst case is about 10 comparisons (log₂ 1024 = 10).
Bubble sort [3, 1, 2] ascending after one full pass: compare 3,1 swap → [1,3,2]; compare 3,2 swap → [1,2,3]. Already-sorted.
Both bubble sort and merge sort produce the same sorted output for the same input — they differ only in process and efficiency, not correctness.
For a sorted list of 8 items the worst case for binary search is 3 comparisons (log₂ 8 = 3).
The author of the algorithm is not a factor that affects its efficiency comparison — only its steps/memory/scaling do.
Linear search can be used on a list of names stored in any order — it makes no assumption about ordering.
Merge sort of [4, 2, 7, 1] first splits into two pairs: [4, 2] and [7, 1].
AQA pseudo-code is language-independent — the exam does not enforce a single strict syntax, only the broad conventions in the AQA reference language document.
Abstraction means removing or hiding detail that isn't needed to solve the problem at hand, focusing only on the essential information.
Trace: x = 5; x = x + 3 → x = 8; x = x × 2 → x = 16. Final x = 16.
Sample questions
A taste of the 119 questions in this topic — answers marked. Sign up to practise the full set with spaced repetition.
What must be true of data before binary search can be used?
- ✓The data must be sorted
- •The data must be stored in a hash table
- •The data must be stored in a linked list
- •The data must contain no duplicate values
What does bubble sort repeatedly do?
- ✓Compares and swaps adjacent items
- •Divides the list into two halves and merges them
- •Inserts each item into its correct position from a sorted sublist
- •Selects the smallest item and moves it to the front
Which is the main advantage of bubble sort over merge sort?
- •It always sorts large data sets more quickly
- •It is faster on every possible input list
- ✓It is simpler and uses less extra memory
- •It uses divide and conquer to split data
Which is faster on large sorted data sets?
- ✓Binary search is faster than linear search
- •Both algorithms take the same time
- •Linear search is faster than binary search
- •Speed depends only on the input data type
Why might one algorithm be preferred over another solving the same problem?
- ✓It is more efficient
- •It produces a different result
- •It requires sorted input data
- •It uses more memory
How does a linear search work?
- ✓Checks items one at a time
- •Jumps to the middle item first
- •Sorts items before searching
- •Splits the list in half repeatedly
Try it for four weeks. Free.
One school. Unlimited classes. No card limit. No teacher limit. If your students aren't practising daily by the end of the trial, you owe us nothing.