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].
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.
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 123 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.