Math Detours · Grade 10 · Around the corner · 26

Algorithms and big-O

Binary search, sorting, and why some problems blow up exponentially while others stay tame.

Name ____________________Date ____________

Tonight's idea

An algorithm is a recipe precise enough for a machine. Two recipes can give the same answer and differ wildly in how long they take. The difference is about how the work grows as the problem grows, not about fast computers.

Take searching. Finding a name in an unsorted list of \(n\) names may take \(n\) looks. If the list is sorted, look at the middle name and throw away the wrong half. Each look halves the list, so about \(\log_2 n\) looks finish the job: precisely, \(\lceil \log_2(n+1) \rceil\) always suffice (\(\lceil x \rceil\) means \(x\) rounded up to a whole number). A million names takes 20 looks. That is binary search.

Take sorting. Bubble sort swaps out-of-order neighbours until nothing moves, about \(n(n-1)/2\) comparisons in the worst case. Merge sort splits the list in half, sorts each half the same way, then merges the two sorted halves in one pass of \(n\) comparisons. Each of the \(\log_2 n\) levels of splitting costs \(n\), so merge sort costs about \(n \log_2 n\).

Big-O. A cost is \(O(f(n))\) if, for large \(n\), it is at most a constant times \(f(n)\). So \(3n^2 + 5n + 100\) is \(O(n^2)\). Big-O ignores constants and keeps the shape of growth: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\), \(O(2^n)\), \(O(n!)\), from slow-growing to explosive.

Watch one: binary search by hand

Find 73 in the sorted list 2, 5, 11, 17, 23, 31, 41, 47, 59, 61, 67, 73, 83, 89, 97 (15 numbers). The middle, the 8th, is 47. Too small, so discard positions 1–8. Seven remain: 59, 61, 67, 73, 83, 89, 97. The middle is 73. Found in two looks. The worst case for 15 items is \(\lceil \log_2 16 \rceil = 4\) looks: 15 → 7 → 3 → 1.

Merge sort on 8 items: one merge of 8, then two merges of 4, then four merges of 2, each level costing 8. Three levels, 24 comparisons at most, against bubble sort's \(8 \times 7/2 = 28\).

sorted: 8 itemslevel 1: merge cost 8level 2: merge cost 8level 3: merge cost 8
Merge sort on 8 items: 3 levels of halving, and merging back up costs 8 at every level, so at most \(3 \times 8 = 24\) comparisons.

Your turn

  1. How many looks does binary search need, in the worst case, for a sorted list of 100 names? 1000? One million? The eight billion people on Earth? Use \(\lceil \log_2(n+1) \rceil\).
  2. Compute \(n(n-1)/2\) and \(n \log_2 n\) for \(n = 1000\), and say how many times faster merge sort is than bubble sort. Then do \(n = 10^9\), rounding freely.
  3. Classify each in big-O: (a) \(7n + 12\); (b) \(n^2/2 + 100n\); (c) \(5 \log_2 n + 3\); (d) \(2^n + n^{10}\); (e) looking up a word in a printed dictionary; (f) checking every pair of students in a class of \(n\) for a shared birthday.
  4. A computer does \(10^9\) simple steps per second. How long does each take: an \(n^2\) algorithm with \(n = 10^6\); an \(n \log_2 n\) algorithm with \(n = 10^6\); a \(2^n\) algorithm with \(n = 60\); an \(n!\) algorithm with \(n = 20\)? Give each in sensible units.

Binary search is the strategy behind mathdetours.com/demos/guess.html.

Stretch: no sort can beat \(n \log n\)

There are \(n!\) possible orderings of \(n\) items, and each comparison has two outcomes, so after \(k\) comparisons a sorting method has told apart at most \(2^k\) orderings. Deduce a lower bound on the worst-case number of comparisons, and compute it for \(n = 5\) and \(n = 10\).

Answers

  1. 100 names: 7 looks (\(2^7 = 128 \ge 101\)). 1000: 10. One million: 20 (\(2^{20} = 1{,}048{,}576\)). Eight billion: 33 (\(2^{33} \approx 8.6 \times 10^9\)).
  2. \(n = 1000\): bubble \(499{,}500\), merge about \(1000 \times 9.97 \approx 9{,}970\), roughly 50 times faster. \(n = 10^9\): bubble \(\approx 5 \times 10^{17}\), merge \(\approx 3 \times 10^{10}\), about 17 million times.
  3. (a) \(O(n)\). (b) \(O(n^2)\). (c) \(O(\log n)\). (d) \(O(2^n)\): the exponential swallows any power. (e) \(O(\log n)\): it is binary search. (f) \(O(n^2)\): there are \(n(n-1)/2\) pairs.
  4. \(n^2\): \(10^{12}\) steps, 1000 s, about 17 minutes. \(n \log_2 n\): \(2 \times 10^7\) steps, 0.02 s. \(2^{60} \approx 1.15 \times 10^{18}\) steps, about 36.5 years. \(20! \approx 2.43 \times 10^{18}\) steps, about 77 years. Same computer; the shape of growth decides everything.

Stretch. You need \(2^k \ge n!\), so \(k \ge \log_2(n!)\). For \(n = 5\): \(\log_2 120 \approx 6.9\), so at least 7 comparisons. For \(n = 10\): \(\log_2 3{,}628{,}800 \approx 21.8\), so at least 22. Since \(\log_2(n!) \approx n \log_2 n - 1.44n\), every comparison sort needs on the order of \(n \log n\) comparisons, which makes merge sort essentially unbeatable.

← PreviousNext: Geometry on a sphere and beyond →