Algorithm complexity – O(log n), O(n), O(n log n), O(n²) and a sorting race

Computer ScienceAlgorithms & Problem SolvingAges 15–16

Use with my class

A chart plots the number of steps against input size n for the functions log₂n, n, n·log₂n and n², alongside comparison counts measured live for bubble sort and quicksort. Students drag the n marker on the chart to read off values, then click Race to watch both algorithms sort the same array at the same step rate: quicksort (n log n) finishes before bubble sort (n²), and the gap grows as n increases. A second screen, Travelling salesperson, places cities on a map and compares brute force, which checks all (n − 1)!/2 tours and soon needs an unreasonable time, with the fast nearest-neighbour heuristic.

Lesson: Evaluating algorithms: operation count versus input size, Big O notation, comparing bubble sort and quicksort

What it shows

Algorithm complexity describes how the number of operations grows as the input size n grows, ignoring constant factors. The chart compares log₂n, n, n·log₂n and n²; measured counts show bubble sort near n²/2 comparisons and quicksort near 1.4·n·log₂n. Some problems are far worse. The travelling salesperson screen tries every tour: (n − 1)!/2 of them, so each extra city multiplies the work and 16 cities would take hours. A heuristic such as nearest neighbour answers in n(n − 1)/2 steps, quickly but not always with the shortest tour.

How to use

Drag on the chart to change n and turn on Log scale when the curves are far apart; press Race to watch the sorts. Then press Salesperson: tap the map to add cities, press Brute force and Nearest neighbour, and compare the tours and steps. Change Number of cities and Computer speed to see the time explode.

Parameters you can change

  • Data size n 4–100
  • Theoretical curves shown log₂n, n, n·log₂n, n², n and n², log₂n, n and n·log₂n, n, n², 2ⁿ and n!
  • Log scale for the step axis
  • Race speed 5–200 steps/s
  • Screen Complexity chart, Travelling salesperson
  • Number of cities (travelling salesperson) 4–16
  • Random seed for the cities 1–999
  • Computer speed 10⁶ steps per second, 10⁹ steps per second, 10¹² steps per second

Questions to explore

  1. When n doubles from 50 to 100, by what factor does n² grow, and roughly by what factor does n·log₂n grow?
  2. Why does the log₂n curve stay almost flat while the n² curve rises steeply?
  3. For n = 10, how many more comparisons does bubble sort make than quicksort, and does the difference matter in practice?