1
$\begingroup$

The randomized quicksort algorithm works as follows:

  • If the list to sort is empty or has length one, it’s sorted.
  • Otherwise, pick a uniformly random element of the list called the pivot element. Partition the list into two smaller lists: items less than the pivot and items greater than the pivot. Recursively sort each and concatenate the list of smaller elements, then the pivot, and finally the list of larger elements together.

A famous result is that quicksort, on average, makes at most $2n H_n$ comparisons when sorting a list of n items, where $H_n$ is the $n\text{th}$ harmonic number. Because $H_n$ is $\ln n + O(1)$, this means that on average quicksort makes at most $2n \ln n + O(n)$ comparisons.

I’ve always been intrigued why the natural logarithm arises here. It’s far more common to see base-2 logarithms in the context of divide-and-conquer algorithms, and the fact that we see $e$ appear here is surprising. (And apparently I’m not the only person who thinks it’s surprising!)

I can follow the derivation of the analysis of quicksort and I am very comfortable with the connection between harmonic numbers and natural logarithms. But if a student asked me why, intuitively, we’d expect to see the natural logarithm arise when analyzing quicksort, I wouldn’t have an explanation for them.

Is there a good intuition as to why of course we would obviously expect the natural logarithm to arise here?

$\endgroup$
1
  • $\begingroup$ $H_n=\sum\limits_{x=1}^n \frac1x$ is similar in structure and magnitude to $\int\limits_{x=1}^n \frac1x\, dx =\log_e(n)$ with the difference between then falling from $1$ towards $ \gamma\approx 0.5772$ as $n$ increases $\endgroup$
    – Henry
    Commented Dec 5, 2023 at 17:07

1 Answer 1

Reset to default
1
$\begingroup$

There is nothing deep going on here.

The pivoting and repeated recursion gives the reciprocals up to $1/n$ when $n$ is factored out in front of the expression. On summing this leads to the harmonic number.

The only reason $\ln n$ shows up is the approximation to $H_n$.

And since $\ln n$ and $\log_2 n$ are proportional you could write the same expression with log to base 2 and a different constant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .