Below is an excerpt from Khan Academy's Quick Sort Analysis page.

excerpt from Khan Academy

In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each time.

So why is it easier to assume $\log_4 n$ levels when the $n$ elements are being partitioned ? Why not assume it to be $\log_2 n$ levels ?

Wouldn't $\log_4 n$ and $\log_2 n$ mean the same thing here ?

  • 3
    $\begingroup$ Please replace the image with text. Images are not searchable. $\endgroup$ – Yuval Filmus Aug 21 '17 at 11:36
  • $\begingroup$ The excerpt, your chosen title, and your question does not seem to have anything to do with each other. The excerpt explains how logarithms work, your title asks about approximation, and in your question you suddently talk about average case and a claim that's not in the excerpt. $\endgroup$ – Raphael Aug 21 '17 at 11:57
  • $\begingroup$ The text explains in some detail why $\log_4 n$ is the appropriate number. What part of it are you having trouble with? Where do you think $\log_2 n$ would come into it? $\endgroup$ – David Richerby Aug 21 '17 at 12:48

No, $\log_4 n$ is not the same as $\log_2 n$. $\log_4$ is exactly $\frac{\log_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log_4 n) = O(\log_2 n)$. But at this point they aren't computing the complexity (yet). They are doing "exact" math. If you have an array with $n$ elements and you always divide it by $4$, it will take exactly $\lceil\log_4 n \rceil$ iterations until you reach the size $1$, and not $\lceil \log_2 n \rceil$.

One more thing. They don't proof, that the average runtime is $\Theta(n \lg n)$. Because the array will obviously not always split with a ratio of 1:3. They only give you some intuition, why the complexity makes sence. Like they mention in the article:

Showing that the average-case running time is also $\Theta(n \lg n)$ takes some pretty involved mathematics, and so we won't go there.

| cite | improve this answer | |

You should forward this question to the authors of the document you refer to. What the text you quote provides is intuition on the performance of quicksort on random inputs. Actual proofs use different approaches (or a much more refined version of the same approach).

For the actual proof, you can refer to slides of Xi Chen, which start with a similar intuition, and then give an actual proof.

Finally, $\log_2n$ and $\log_4n$ are the same up to constant factors, that is $\log_2n = \Theta(\log_4n)$, but sometimes we are interested in the hidden constants; for example, we might be interested in the average number of comparisons, and use this to compare different algorithms.

| cite | improve this answer | |
  • $\begingroup$ I actually did forward the question to the original authors, but unfortuanately I didnt get any response hence posting here was my last option $\endgroup$ – ng.newbie Aug 22 '17 at 17:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.