random cover of a range

[Jason House]

Andrei Alexandrescu Wrote:

> Ok, following Leonardo's and Denis' ideas on covering an immutable array 
> in random order, I thought about it and came up with one algorithm, in 
> addition to the obvious one that stores one integer per element (see 
> Denis' code).
> 
> Here's the algorithm. It stores one bit per element and takes O(n log n) 
> time to cover a range of length n.
> 
> 1. Given a random-access range r of length n, create a bitmap with one 
> bit per element in r. The range is initially all zeros.
> 
> 2. At each step, select a random index in the _original_ array, i.e. a 
> random number in 0 .. r.length. Then walk upwards (with wrapping at the 
> end of the range) until you find a bit = 0 in the bitmap. Mark that bit 
> = 1 and return the found element.
> 
> 3. The cover ends when all bits in the bitmap are 1.


So far so good.


> I did a ballpark complexity estimate by approximating the average number 
> of steps in (2) with n / (n - k), where k is the number of 1s in the 
> bitmap. IIRC the average number of steps to hit a 1 in a binomial 
> distribution with p = (n - k) / n is 1/p. Right? In that case, the total 
> number of steps taken by the algo above is:
> 
> N = n / 1 + n / 2 + ... + n / (n - 1) = n * (1 + 1/2 + 1/3 + ... + 1/(n 
> - 1)) < O (n log n)
> 
> Makes sense?


No.  Your wording sounds like you're doing stuff that's way off, but the resulting math is correct.  My calculation would be based on the average length of a sequence of 1's (k/(n-k)).  That means the work is 1+k/(n-k) = n/(n-k).

Given that O(n*log(n)) is the theoretical best you can do, having a result that is < O(n*log(n)) is highly suspect.  The sum 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... is in fact O(log(n)).  



> If the range does not offer random access, I think this algorithm will 
> have quadratic complexity because it needs to make a number of steps 
> proportional to n at each iteration.

That's when copying may be the best implementation