On Wednesday, 22 July 2015 at 16:59:29 UTC, Xinok wrote:
On Saturday, 11 July 2015 at 02:56:55 UTC, Timon Gehr wrote:
[...]
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.
[...]
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.
I haven't looked at the paper, but # followed by a set often
means cardinality, i.e. (assuming the set is is finite) the
number of elements in the set.
