0
$\begingroup$

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$,

The reason for this bound is that those algorithms are using the division by two devide and conquer method and as such they generate a binary tree that begins at a root and from there on branches two times from each node until it reaches the bottom to produce exactly $n$ leaves at the bottom level.

Since it is a binary tree, it has exactly $log_{2}(n)$ levels from the root down to the leaves and as such it costs $log_{2}(n)$ "computational decisions" to generate the tree and $n$ decisions to walk over all leaves, so $n*log_{2}(n)$ looks absolutely valid at first.

I don't argue about the factor $n$ before the $log_{2}(n)$, what I argue about is, why is it everywhere such a strict advocating consensus about to always use $log_{2}(n)$ in computer science.

Imagine for example instead if I don't use the binary devide&conquer method, but if I adress the indices of the list which are prime numbers, using the values of those indices as representational values to compute the differences of the indices between the primes. The resulted tree structure from such an algorithm will have many more branches than two at most of the nodes and the generated tree size will be much much lower.

An computational approximation of an list with 1000000000 and the assumption of having 10 splits instead of two would result in 270 times less computational decisions when the $log_{10}(n)$ insead of the $log_{2}(n)$ would be used and I'm quite confident that this can be relaxed to an even much smaller tree in general, if I'm not oversimplifying it at least.

$\endgroup$
2
$\begingroup$

Fist of all the $\Omega(n \log n)$ lower bound only applies to comparison-based algorithms, that is only to algorithm that can only obtain information on the relative orders of two input elements by pairwise comparisons.

They do not have to be divide and conquer algorithms and they do not have to generate any tree. The lower bound simply follows from the fact that there are $n!$ possible permutations of the input elements and any correct algorithm must be able to output all of them (given the inverse permutation as its input). This means that the number of branches on the longest computation of the algorithm must be at least: $$ \log ( n! ) > \log (n/e)^n = n \log n - n \log e > n \log n - 1.44 n = \Omega(n \log n). $$

Also, even in the case of comparison based-algorithms, an absolute lower bound of $n \log n$ (without the constant hidden in the $\Omega(\cdot)$ notation, as you write in the question) on the number of comparisons cannot possibly exist since, when $n=2^k$, each element in Mergesort is compared at most $k-1$ times, showing that the total number of comparisons is at most $n(k-1) = n \log n - n$.

Your proposed algorithm is not clear to me but, in general, if you change the model of computation by allowing other operations to be performed in addition to comparisons then the $\Omega(n \log n)$ lower bound does not apply anymore.

For example, given any constant $c$, in the word-RAM model you can sort a collection of $n$ elements between $0$ and $n^c$ in linear time using Radix sort, as long as the chosen word size $w$ allows to write $n$ in a (constant number of) memory word(s), as it is usually the case (it is standard to assume $w=\Theta(\log n)$).

$\endgroup$
3
  • $\begingroup$ What I tried to illustrate is that it can be derived from computational comparison of the prime index values where exactly the nonprime index values have to be guided. For example if there is some value at the prime index 3 which is smaller then the index value at 5 but greater than the index value at 11. $\endgroup$ – Eugen Jan 14 at 16:59
  • $\begingroup$ Now with this information I'm inspecting the value at the nonprime index 161, 161 = 3*5*11, but to guide the value of this position into the right direction, I don't have to compare it with all of the 3 prime index values and the same "information recycling" applys when I proceed further and inspect the value at the nonprime index 322 = 161*2 = 2*3*5*11 to guide it into the right direction. $\endgroup$ – Eugen Jan 14 at 17:00
  • $\begingroup$ One thing that I may have oversimplifyed might be the additional requirement of knowing every prime number of the list and every factorization of each non prime index, calculating those requirements for each new list would definetly be a huge computational waste, but on the other side, this problem could be trivialized by having access to a database where this information is stored for an practically needed amount of numbers. $\endgroup$ – Eugen Jan 14 at 19:27

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.