Constant Shaving on known algorithms

Question

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.

Answer 1

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").