On 07/11/2015 02:32 AM, Xinok wrote:
On Friday, 10 July 2015 at 21:26:50 UTC, Timon Gehr wrote:
I think this method is likely to be less practically relevant than the
one they improve upon. (log* n really is constant for all practical
purposes, it is the number of times one needs to iteratively take the
logarithm until a number below 1 is obtained.)
log* n grows fast for small inputs,
No, it does not. It has no space to grow. With base e, it is 3 or 4 for
all input sizes that matter:
http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^8
http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^32
http://www.wolframalpha.com/input/?i=plot+IteratedLog+from+0+to+2^64
http://www.wolframalpha.com/input/?i=IteratedLog%282^2^2^2^2%29
so we can't simply ignore it.
There is a priori no practical difference between a O(n) algorithm and a
O(n*log*(n)) algorithm. It all depends on the constants, and it is hence
not clear-cut that the O(n) algorithm will run faster.
I'm just saying that this should be taken into consideration.
For example, if n = 2^16 = 65536, then n*lg(n) = 16*2^16 = 2^20 = 1048576.
...
The algorithm runs in O(n*log*(n)). It's not n log(n).
That paper appears to be available here:
https://github.com/lispc/lispc.github.com/raw/master/assets/files/situ.pdf
No idea what the constant is though, I have not read the paper (yet).
I don't know if there is anything relevant but that paper focuses on a
different problem involving sorting.
No, it focuses on a few closely related problems, and the
O(n*log*(n))-algorithms solves a problem that is a straightforward
generalization of the problem you are looking at. Stable three way
partition is stable sorting where there are only three "distinct" values
(smaller, equal, greater). The paper you provided builds on top of this
algorithm. It is the main reference and part (ii) of the "Algorithm B"
part of the O(n)/O(1) algorithm does not occur in the paper you
provided, but only in that other paper, so yes, it is relevant. :-)
