Popular Posts

Tuesday, August 9, 2011

CLRS Exercises 5.1-2

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:

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

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

3 comments:

  1. What is the need for while loop?

    Take 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)).

    ReplyDelete
  2. can you explain the time complexity

    ReplyDelete