Lesson 4: Counting the cost

Derive n(n - 1)/2 on the board, then show learners what quadratic feels like.

~10 minutes. Builds on Lesson 3.

Count the comparisons

Pass 1 compares n - 1 pairs, pass 2 compares n - 2, down to pass n - 1 which compares 1. Sum:

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

That is the worst case and, without early exit, every case. For n = 10 it is 45; for n = 100 it is 4,950; for n = 1,000 it is 499,500. Growth is O(n²): 10x the input, 100x the work.^[1]

Swaps

Swaps equal the number of inversions: pairs that are out of order. Reverse-sorted input has n(n - 1)/2 of them, so swaps are also O(n²) in the worst case. Each swap fixes exactly one inversion, never more.

Feel it

Measured comparisons and swaps on random input of size n, run in your browser now.

Why nobody ships it

Merge sort and the library sort in every runtime are O(n log n). At n = 1,000,000 that is roughly 2 x 10⁷ steps versus 5 x 10¹¹ for bubble sort: about 25,000x. Even among O(n²) sorts, insertion sort beats it in practice (next lesson).^[2]

Retrieval practice

Primary source

MIT OCW 6.100L Lecture 24 puts bubble, selection and merge sort side by side. Also drag the size slider on the USF visualizer.

Anything unclear? Ask your teaching agent - it wrote this lesson and can go deeper on any point.