**Problem:**

Describe an implementation of the procedure RANDOM(a, b) that only makes calls to

RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and

b?

**Solution:**

- n = ceil(log(b-a+1))
- decimal_number=0;
- do
- for i = 1 to n: get all binary
- decimal_number = generate decimal from binary digits
- while decimal_number > b-a+1
- return decimal_number

**Complexity:**Θ(log (b-a+1))

What is the need for while loop?

ReplyDeleteTake n as floor(b-a+1).

Let r be the generated number.

Then,

0 <= r <= 2^(floor(b-a+1)) - 1

<= 2^(b-a+1) - 1

= b - a + 1 - 1

= b - a

So,

a <= r + a <= a + b - a

<= b

So, r + a is random number that satisfies the required conditions.

And complexity is of course Θ(log (b-a+1)).

Nope...sorry....made a mistake...

ReplyDeletecan you explain the time complexity

ReplyDelete