On Saturday, 11 July 2015 at 02:56:55 UTC, Timon Gehr wrote:
...
The algorithm runs in O(n*log*(n)). It's not n log(n).
...
I understand now. I had never heard of an iterated logarithm
before. I took the asterisk to mean some constant, like a wild
card if you will. Sorry for the confusion.
I wonder if the true O(n) algorithm is still worth pursuing.
Although log*(n) may only be a factor of 2 or 3, the O(n)
algorithm may have a small constant factor which makes it 2-3x
faster.
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. :-)
I get that much now, but this paper is still way above my head.
There's some notation in the sample code that I don't understand.
In this statement:
e <- #{ j : L[j] = x, 1 <= j <= n }
I'm not sure what the pound # signifies or what exactly is being
assigned to e. I'm assuming it performs some operation on the
set, like "max", but I'm not sure what.
