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
The author of the algorithm is not a factor that affects its efficiency comparison — only its steps/memory/scaling do.
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.
Trace Tables and Algorithm Walkthroughs
Trace: x = 5; x = x + 3 → x = 8; x = x × 2 → x = 16. Final x = 16.
Sample questions
A taste of the 109 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?
- ✓Bubble sort
- •Linear search
- •Merge sort
- •Temperature 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
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.