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, so we can't simply ignore it.
For example, if n = 2^16 = 65536, then n*lg(n) = 16*2^16 = 2^20 =
1048576.
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.
