Fundamentals of Algorithms
What's covered
Key facts
Binary Search
For 1,024 sorted items the worst case is 11 comparisons (floor(log₂ 1024) + 1).
Bubble Sort
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.
Comparing Bubble Sort and Merge Sort
Both bubble sort and merge sort produce the same sorted output for the same input: they differ only in process and efficiency, not correctness.
Comparing Linear and Binary Search
For a sorted list of 8 items the worst case for binary search is 4 comparisons: 8, then 4, 2 and finally 1 remaining item (floor(log₂ n) + 1).
Efficiency of Algorithms: Comparing Alternatives
An algorithm's efficiency is judged by the time (number of steps) and memory it needs and how these grow with input size; who wrote it is irrelevant.
Insertion Sort
Unlike bubble sort, insertion sort does not guarantee the largest item reaches the end after the first pass; the largest item may be inserted last.
Linear Search
On average, in a random list of n items with the target present, linear search examines about n/2 items.
Merge Sort
Merge sort of [4, 2, 7, 1] first splits into two pairs: [4, 2] and [7, 1].
Pseudo-code, Flowcharts and Program Code
An algorithm is a sequence (an ordered set) of steps to complete a task: "a set of instructions" is too vague because order matters. An algorithm is not the same as a program; a program is one implementation of an algorithm.
Representing Algorithms: Decomposition and Abstraction
Abstraction means removing or hiding detail that isn't needed to solve the problem at hand, focusing only on the essential information.
Practice questions with answers
A taste of the 113 questions in this topic, answers marked. Sign up to practise the full set with spaced repetition.
What must be true of a list before a binary search can be used on it?
- •It must be a very short list
- •It must be left unsorted
- ✓It must be sorted into order first
- •It must contain only numbers
An algorithm repeatedly compares adjacent items and swaps them if out of order. Which sort is it?
- •Binary search
- ✓Bubble sort
- •Linear search
- •Merge sort
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
Which description matches how insertion sort works?
- ✓Inserts each item into its correct place in a sorted section
- •Picks a middle item and splits the list around it
- •Splits the list into single items then merges them back
- •Swaps neighbouring items repeatedly until no swaps are made
Three minutes a day. Knowledge that sticks.
Practise all 113 Fundamentals of Algorithms questions with spaced repetition, so what you revise today is still there in the exam. Free to use, no card needed.