What is the time complexity of this аlgorithm? O(n * r) Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function rand5 which should return random integer in interval [0, 4] using function rand7.


This is a question from my book. So, this is how I solved it (the algorithm is written in C):

int rand5(void){
  return (int)(rand7() * 4. / 6. + .5);
}


Basically, I just scaled the interval to [0, 4]. The + .5 part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.

Solution in my book is very weird to me. This is how they did it:

int rand5(void){
  int a;
  while((a = rand7()) &gt; 4);
  return a;
}


The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.

Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is O(r) where r is time complexity of rand7. But what is the complexity of their algorithm?

The complexity should be O(r * n) where n is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function rand7 and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is O(infinity) which doesn't make any sense.

Of course, if rand7 if properly implemented, it will for sure return at lest one time number in interval [0, 4]. But, theoretically, it can return any number of consecutive numbers which belong in interval [5, 6]. Is then complexity indeterminate?

Also, how is that possible that "there is no other solution"? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval [0, k] for given number k using only rand2 (for example), such that the algorithm should work in finite time complexity?

Edit

Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?
Investigating worst-case cost is rarely useful for randomized algorithms. Here, the worst case is indeed that the loop never stops -- but this event has probability zero!

Instead, perform average-case analysis. What is the probability of the loop running $k$ times?


   That means it misses the interval $k-1$ times, and then hits it. Assuming that rand7 has indeed uniform distribution, the probability of the former is $\frac{2}{7}$, and of the latter $\frac{5}{7}$. The result is, assuming that separate calls of rand7 are stochastically independent, $\bigl(\frac{2}{7}\bigr)^{k-1} \cdot \frac{5}{7}$.


Now you compute the expected number of iterations using basic facts from stochastics.


   The above weights are those of a geometric distribution. Looking up its properties, we learn that its expected value is $\frac{7}{5}$.


As it turns out, this is not too bad. You can also investigate the standard deviation or compute some probabilities to get a feeling for how unlikely high iteration counts are.