Many algorithms for one problem
An algorithm is a set of exact steps to solve a problem. Most problems can be solved by more than one algorithm. For example, to find a name in a list you can check every name, or (if the list is sorted) you can keep halving it.
Both give the right answer. The difference is efficiency: how much work and memory each one needs. A good programmer picks the algorithm that stays fast when the data becomes big.
Comparing algorithms by time taken
Timing with a stopwatch is not fair: a fast computer makes a slow algorithm look good. So we count basic steps (comparisons, swaps, additions) as a function of the input size n.
Best, average and worst case
The best case is the luckiest input (13 is in the first box: 1 step). The worst case is the unluckiest (13 is not there: n steps). We usually quote the worst case, because it is a promise: the algorithm will never be slower than this.
Time complexity and space complexity
Time complexity tells how the number of steps grows with n. Space complexity tells how the extra memory grows with n. Merge sort is fast but needs extra memory; bubble sort needs almost no extra memory but is slow.
Big O notation
Big O describes the growth rate, ignoring small details. We keep only the biggest term and drop constant numbers: 3n² + 5n + 2 becomes O(n²), because for big n the n² part is almost everything.
| Big O | Name | n = 16 | n = 1000 | Example |
|---|---|---|---|---|
| O(1) | constant | 1 | 1 | read item 5 of an array |
| O(log n) | logarithmic | 4 | about 10 | binary search |
| O(n) | linear | 16 | 1000 | linear search, find the largest |
| O(n log n) | n log n | 64 | about 10,000 | merge sort |
| O(n²) | quadratic | 256 | 1,000,000 | bubble sort, nested loops |
Quick rule for code: one loop over n items is O(n); a loop inside a loop is O(n²); halving the problem each time is O(log n).
Efficiency of linear and binary search
Linear search checks items one by one. Worst case: n comparisons, so O(n). It works on any list, sorted or not.
Binary search needs a sorted list. Look at the middle; if it is too big, throw away the right half, else the left half. Each step halves the list, so the worst case is about log₂ n + 1 comparisons: O(log n). For 1,000,000 items that is about 20 steps instead of 1,000,000.
Efficiency of sorting algorithms
Bubble, insertion and selection sort use a loop inside a loop, so they take about n²/2 comparisons: O(n²). Insertion sort is O(n) in the best case (an already sorted list).
Merge sort halves the list about log₂ n times and does about n work at each level: O(n log n). It needs O(n) extra memory.
Binary search needs a sorted list. If you search only once, sorting first (n log n) costs more than one linear search (n). If you search many times, sorting once pays off.
Preconditions, postconditions and recursion pitfalls
A precondition is what must be true before the algorithm starts (binary search: the list is sorted). A postcondition is what is promised when it ends (sorting: every item is less than or equal to the next). Writing them down helps you test and prove an algorithm.
Recursion means a function calls itself on a smaller problem. Common mistakes:
- No base case, or a base case that is never reached: the calls never stop (stack overflow).
- The problem does not get smaller on each call.
- Repeating the same work: a simple recursive Fibonacci calls fib(3) again and again, so it grows like O(2ⁿ). Storing answers (memoisation) makes it O(n).
- Very deep recursion uses a lot of memory, one stack frame per call.
Try it: race two searches
Write the numbers 1 to 32 on paper slips and put them in order face down. Ask a friend to pick a secret number. First search one by one and count the slips you turn. Then search by always turning the middle slip. Repeat 5 times. Which method never needed more than 6 turns? Check with the slider in the last 3D step (n = 32: log₂ 32 = 5).
Key formulas and definitions
- Linear search: worst case n comparisons → O(n)
- Binary search: worst case about log₂ n + 1 comparisons → O(log n)
- Bubble / insertion / selection sort: about n(n − 1)/2 comparisons → O(n²)
- Merge sort: about n log₂ n comparisons → O(n log n)
- Big O rule: keep the biggest term, drop constants (5n² + 3n → O(n²))
- Doubling n: O(1) same, O(log n) +1, O(n) ×2, O(n²) ×4
Worked examples
1. A list has 50 names. How many comparisons does linear search need in the best and worst case?
Best case: the name is first → 1 comparison. Worst case: the name is last or missing → 50 comparisons. Linear search is O(n).
2. What is the most comparisons binary search needs for a sorted list of 1024 items?
Each step halves the list: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. That is 10 halvings, plus the last check: at most 11 comparisons (log₂ 1024 = 10).
3. Give the Big O of f(n) = 4n² + 10n + 7.
Keep the biggest term (4n²) and drop the constant 4: O(n²).
4. A loop runs i from 1 to n, and inside it another loop runs j from 1 to n. How many times does the inner line run?
n times for each of n values of i: n × n = n². Time complexity O(n²).
5. An O(n²) program sorts 1000 items in 2 seconds. Roughly how long for 3000 items?
n becomes 3 times bigger, so n² becomes 3² = 9 times bigger: about 2 × 9 = 18 seconds.
6. Compare bubble sort and merge sort for n = 1000 items.
Bubble sort: about n²/2 = 500,000 comparisons. Merge sort: about n log₂ n = 1000 × 10 = 10,000. Merge sort does about 50 times less work, but needs extra memory.
Common mistakes
- Measuring speed only with a stopwatch on one computer. Count steps against n instead.
- Using binary search on an unsorted list. Its precondition is a sorted list.
- Keeping constants in Big O, like writing O(2n). It is just O(n).
- Writing a recursive function with no base case, or one that does not make the problem smaller.