For homework, the task is to verify the time complexity of quicksort. User Nick suggested on quora that one could check the number of comparisons made when doubling the input size. If the comparisons increase by a factor of around 2, we verify that quicksort has $O(n \log n)$ time complexity.

Is this a legitimate method to verify the time complexity?


Let's denote by $C(n)$ the number of comparisons performed on an input of length $n$ (later on I will comment more on this definition). The assumption that the number of comparisons roughly doubles when doubling the input size translates to $C(2n) \approx 2 C(n)$. This is not a precise statement, so let us take it to mean that $$ \lim_{n\to\infty} \frac{C(2n)}{C(n)} = 2. $$ There are many functions satisfying this statement. Some examples are $n (\log n)^k$, for any value of $k$. This condition cannot distinguish between algorithms with a linear number of comparisons and those with $n\log n$ or $n\log^2 n$ comparisons, and in particular cannot imply that quicksort uses $O(n\log n)$ comparisons.

Let $D(n) = \log[C(n)/n]$, so that $$ \lim_{n\to\infty} [D(2n) - D(n)] = 0. $$ What we can conclude is that $D(n) = o(\log n)$, which translates to $C(n) = n 2^{o(\log n)}$.

Another problem with your analysis is that the number of comparisons could depend on the input, not only on the input size. In other words, $C(n)$ is not well-defined. It is known that quicksort has worst case number of comparisons $\Omega(n^2)$, but the average number of comparisons (over a random permutation) is only $\Theta(n\log n)$. We usually take $C(n)$ to be either the worst case number of comparisons or the average number of comparisons (for a random permutation).

Yet another problem is that it's not clear how to establish $C(2n)/C(n) \to 2$. Is this the result of an experiment, a heuristic calculation, or a formal proof? You don't make it clear. Experiments might show that $C(2n) \approx 2C(n)$ for small $n$, but the asymptotic behavior might be different; $C(2n)/C(n)$ might grow slowly, but eventually tend to infinity, for example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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