The algorithm is as follows:

a = rand  % a random number between 0 and 1
b = a
while b == a
    b = rand

Here rand is a function that returns a random number, generated uniformly, between 0 and 1. Let us say that this is the MATLAB function rand.

What is the time complexity of this algorithm?

It looks like the best and average complexities are $O(1)$ and the worst complexity is unbounded.

  • 3
    $\begingroup$ Complexity in what model of computation? What form might the numbers $a$ and $b$ take? What exactly does rand do? In most actual programming languages, it gives a pseudorandom number so there are actually deterministic bounds on exactly how long it will take to get back to the initial value. $\endgroup$ – David Richerby Jun 23 '16 at 15:05
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Jun 23 '16 at 17:47
  • $\begingroup$ Duplicate? $\endgroup$ – Raphael Jun 24 '16 at 10:39

rand () is probably a random number generator, but the details are unknown. Since we don't know how exactly rand () behaves we don't know how long this will take.

I would assume that with many random number generators it is possible to prove that rand () will not be called more than three times (that is there is no state where rand () would return the same value three times in a row). Obviously if you use something like Mersenne Twister with thousands of bits of state, a rather lengthy sequence of identical numbers will happen in some states.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.