The average number of operations needed for quicksort to sort a list of *n* items is approximately 10 times the *n*th prime number.

Here’s some data to illustrate this:

```
|------+-----------------+---------|
| n | avg. operations | 10*p(n) |
|------+-----------------+---------|
| 100 | 5200.2 | 5410 |
| 200 | 12018.3 | 12230 |
| 300 | 19446.9 | 19870 |
| 400 | 27272.2 | 27410 |
| 500 | 35392.2 | 35710 |
| 600 | 43747.3 | 44090 |
| 700 | 52297.8 | 52790 |
| 800 | 61015.5 | 61330 |
| 900 | 69879.6 | 69970 |
| 1000 | 78873.5 | 79190 |
| 1100 | 87984.4 | 88310 |
| 1200 | 97201.4 | 97330 |
| 1300 | 106515.9 | 106570 |
| 1400 | 115920.2 | 116570 |
| 1500 | 125407.9 | 125530 |
| 1600 | 134973.5 | 134990 |
| 1700 | 144612.1 | 145190 |
| 1800 | 154319.4 | 154010 |
| 1900 | 164091.5 | 163810 |
| 2000 | 173925.1 | 173890 |
|------+-----------------+---------|
```

The maximum difference between the quicksort and prime columns is about 4%. In the latter half of the table, the maximum error is about 0.4%.

What’s going on here? Why should quicksort be related to prime numbers?!

The real mystery is the prime number theorem, not quicksort. The prime number theorem tells us that the *n*th prime number is approximately *n* log *n*. And the number of operations in an efficient sort is proportional to *n* log *n*. The latter is easier to see than the former.

A lot of algorithms have run-time proportional to *n* log *n*: mergesort, heapsort, FFT (Fast Fourier Transform), etc. All these have run time approximately proportional to the *n*th prime.

Now for the fine print. What exactly is the average run time for quicksort? It’s easy to say it’s O(*n* log *n*), but getting more specific requires making assumptions. I used as the average number of operations 11.67 *n* log *n* – 1.74 *n* based on Knuth’s TAOCP, Volume 3. And why 10 times the *n*th prime and not 11.67? I chose 10 to make the example work better. For very large values on *n*, a larger coefficient would work better.

## {{ parent.title || parent.header.title}}

## {{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}