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:
Complexity: Θ(log (b-a+1))
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