Lesson 4 of 4

Growth rates and big-O.

About 25 minutes · 6 practice questions

Read the full article: Algorithms and sorting

What happens to the work when the list doubles: bubble sort grows like the square of the length, and merge sort only a little faster than the length itself. The graph that compares them, big-O notation, and why a good algorithm beats a fast computer.

Step 1 of 6 · Doubling the list

Step 1 of 6

Doubling the list

How long a sort takes depends on the computer, but the number of comparisons does not. So we ask a question that does not depend on the computer: when the list doubles, by how much does the work grow? The answer is the algorithm’s growth rate.

To the question

Step 2 of 6

Doubling with merge sort

Bubble sort compares pairs, and the number of pairs grows fast. Merge sort works differently: $\log_2 n$ ⁠ levels, and at each level work in proportion to $n$ ⁠. Together, about $n \log_2 n$ ⁠.

To the question

Step 3 of 6

The growth board

Show how it grows is on Growth: a glass board rises over the stand with the number of comparisons against List size. The orange ribbon is $\dfrac{n(n-1)}{2}$ ⁠, every pair; the blue ribbon is $n \log_2 n$ ⁠; the white curve is the algorithm you chose, averaged over several starting rows; and the dot is the sort running now.

To the question

Step 4 of 6

Big-O

To talk about growth rates without exact numbers, we write big-O: keep only the fastest-growing term, and drop the constant factors. Linear search is $O(n)$ ⁠, binary search $O(\log n)$ ⁠, and merge sort $O(n \log n)$ ⁠.

Change Algorithm and Starting order and compare the white curve with the two ribbons.

To the question

Step 5 of 6

Finding the size

When the formula is known, you can also go backwards: from the amount of work to the size of the list.

To the question

Step 6 of 6

A better algorithm

The difference between $n^2$ ⁠ and $n \log n$ ⁠ looks small at sixty-four blocks. At a million it is enormous: $\dfrac{n^2}{2}$ ⁠ is about $5 \times 10^{11}$ ⁠, and $n \log_2 n$ ⁠ about $2 \times 10^7$ ⁠.

To the question

Still of the Algorithms and sorting 3D scene

Interactive scene

Loading the interactive version…

Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.

To the experiment

Practice · Predict, then look

Bubble sort on a Reversed row of 16 blocks makes 120 comparisons. List size will double to 32. How many comparisons will there be?

To the experiment

Practice · Predict, then look

Now Merge: on a Reversed row of 16 blocks it makes 32 comparisons. What will happen when List size doubles to 32?

To the experiment

Practice · Calculate

Show how it grows is on Growth: the orange ribbon is $\dfrac{n(n-1)}{2}$ ⁠, the number of pairs. Bubble sort on a Reversed row of 64 blocks compares every pair once. How many comparisons is that?

To the experiment

Practice · Choose

On a reversed row bubble sort makes $\tfrac12 n^2 - \tfrac12 n$ ⁠ comparisons. How is that written in big-O notation?

To the experiment

Practice · Reach the target

Bubble, Reversed. Change List size until the sort makes exactly 190 comparisons, and press Check.

To the experiment

Practice · Choose

A million shuffled items have to be sorted. Computer A does $10^9$ ⁠ comparisons a second and runs bubble sort, about $5 \times 10^{11}$ ⁠ comparisons. Computer B is a hundred times slower, $10^7$ ⁠ comparisons a second, and runs merge sort, about $2 \times 10^7$ ⁠ comparisons. Which finishes first?