0

I was just browsing some great posts here and there online and just started wondering if there is an algorithm that generates random positive numbers, ranging from 0-infinite.

I've seen the Fisher-Yates algorithm that creates an array of numbers in order and shuffles within O(n).

Just out of curiosity, what would be the time complexity of the following pseudocode?

ranNumGenerator(int n) {
repeat until you get n random numbers {
  create randNumArray
  generate a random positive number (range 0-largest integer available)
  if !(randNumArray contains the generated number)
    add to randNumArray
  }
}

I can't seem to figure out what would be its time complexity, neither how I would make it better and more efficient.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
Minjae
  • 31
  • 1
  • 2
  • 8
  • Are you assuming it takes constant time to generate one random integer? Notice that if we begin with random bits, then generating an integer in [0, `n`) with those bits has an unbounded worst-case time complexity unless `n` is a power of 2. See also: https://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits/62920514#62920514 – Peter O. Jan 11 '21 at 19:53
  • I mean, just select a random number _normally_ and double it? – Steven Jan 11 '21 at 20:07
  • If you mean _uniformly_ random, then it's impossible. If you choose a distribution with infinite tail, then just use the method of inverse CDF (e.g. for exponential, see this: https://stackoverflow.com/a/2106564/1161878). The time bound depends on the machine model you choose. – Gene Jan 12 '21 at 04:04
  • your chunk of code (when repaired the pre-allocation should be before the repeat) is `O(n^2)` also assuming random is `O(1)` and array is pre-allocated. In case you use ordered array and binary search you get `O(n.log(n))` instead. The shuffling is indeed `O(n)` and might be randomized even further (you generate uniformly distributed points for the range and add random value smaller then the distance betweeen consequent points that is still `O(n)` ) – Spektre Jan 12 '21 at 10:33

1 Answers1

2

Best case - linear: every time you generate a number, it is not in the randNumArray.

Worst case - unbounded: every time you generate a number, it is in the randNumArray.

Average case. Let N be the size of the array, and let P be size of puul from which the random numbers are sampled. Let T(N, P) be the time to generate such an array. Then T(N+1, P) = T(N, P) + t(N, P) where t(N, P) is an expected number of tries to generate a number not in the array:

t(N, P) =
    1 * (P-N)/P +
    2 * (N/P) * (P-N)/P + 
    3 * (N/P)^2 * (P-N)/P +
    ... +
    k * (N/P)^{k-1) * (P-N)/P +
    ... =
    (P-N)/P * Sum k * (N/P)^{k-1}

After a bit of algebra (which I don't want to spell here in lieu of LaTeX support),

t(N,P) = P/(P-N)

so T(N+1, P) = T(N, P) + P/(P-N) = Sum[k = 1..N] P/(P-k)

Now, if P is much larger than N, the sum is slightly larger than N. If P is a tad larger than N, the sum is very close to P log P.

user58697
  • 7,808
  • 1
  • 14
  • 28
  • I'm having trouble seeing why your last statement isn't that it's close to `P ln P`, since your final sum is eqivalent to `P` times the `N`th harmonic number as `N -> P`. (See https://math.stackexchange.com/a/451668) – pjs Jan 11 '21 at 20:47
  • @pjs A typo, thanks for catching. I was sure I already lifted `P` out of the sum. Surely, the total complexity is `P log P`. – user58697 Jan 11 '21 at 23:27