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

What it shows

Algorithm complexity describes how the number of operations grows as the input size n grows, ignoring constant factors. The chart compares four growth rates: log₂n barely rises, n grows in proportion, n·log₂n grows a little faster, and n² quadruples every time n doubles. Measured counts back up the theory: on a random array bubble sort makes about n²/2 comparisons, while quicksort makes about 1.4·n·log₂n. For small n the difference hardly matters; for large data sets the choice of algorithm decides whether a program finishes in seconds or in hours.

How to use

Start with Theoretical curves shown set to all four functions and drag on the chart to change n, reading the values for each curve. When the curves are too far apart to compare, turn on Log scale for the step axis. Then press Race so both algorithms sort the same array at the same step rate, and repeat with New array and a larger n to see how the gap between them widens.

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
• Log scale for the step axis
• Race speed 5–200 steps/s

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?