3
$\begingroup$

Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving constants. Are there any really non trival, perhaps not practical sorts, that have excellent constant performance? For example do there exist algorithms that say achieve $\frac{1}{2} n \log(n)$ number of comparisons as opposed to say mergesorts $1.44 n \log(n)$, and can this leading constant, be reduced arbitrarily low?

It oculd be the case these algorithms have running time

$$ 0.0001 n \log(n) + 9^{\text{Graham's Numbers}}n + \pi^{\pi^\pi} $$

But I am still curious if non trivial reduction of constants exists, or if someone has proven tight bounds on what the constants must be.

$\endgroup$
  • 1
    $\begingroup$ There are tools one can use to prove tight lower bounds under believed or debatable complexity assumptions. For example, these are of the type "you can't get a $c^n$-time algorithm for a particular problem for any $c < 2$". Such results are often found in the context of hard problems, but you might as well show tight bounds for problems in P as well, see e.g. this FOCS'14 paper. $\endgroup$ – Juho Nov 13 '15 at 6:14
  • $\begingroup$ You want to use $\Omega$ in the first line. $\endgroup$ – Raphael Nov 13 '15 at 8:11
  • 2
    $\begingroup$ Of course there is a community that tries to improve constant factors! Just look at all the recent work on multi-pivot variants of Quicksort. Mind that there are lower bounds for constant factors as well, though. Anyway, your question feels too broad to me (but you probably did not realize this), at least the title. Are you mostly interested in sorting at this point? $\endgroup$ – Raphael Nov 13 '15 at 8:14
4
$\begingroup$

Let's suppose that you want to do comparison-based sorting of $n$ distinct elements.

You can interpret the problem in terms of information theory. You want to discover which permutation the sequence is currently in. That is, you need to discover a number between $1$ and $n!$.

The comparison operator gives you one bit of information. But to discover a number between $1$ and $n!$, you need at least $\log_2 n!$ bits of information. Therefore, you need at least $\log_2 n!$ comparisons.

By Stirling's approximation:

$$\log_2 n! = n \log_2 n - \frac{n}{\ln 2} + O(\log n)$$

This is the number of comparisons you need. You cannot do better than this. For any comparison-based sort which takes $k n \log_2 n + o(n \log n)$ comparisons, $k \ge 1$. In particular, there is no comparison-based sort which uses $\frac{1}{2} n \log_2 n$ comparisons.

So no, you can't reduce constants arbitrarily.

We usually don't do this kind of analysis for time complexity, because in practice, "time" depends on many factors like the compiler settings, the CPU architecture, the laws of physics, and so on. However, it becomes very important when analysing space complexity; we do measure time in physical units ("this program will take three hours to run"), but we don't typically measure space the same way ("I need a cubic metre of disk").

| cite | improve this answer | |
$\endgroup$

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.