Hey, I spend most of my time researching systems computing, but these
problems are fun and interesting (so bare with me :)
This problem is from Chapter 5 of Introduction to Algorithms (MIT
Press)
5.1-2
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?
Here is my approach...
It's asking for the expected running time of the procedure, and the
expected value is
E[X] = sum (0 to n) x*p(x)
In this case n = b-a+1
p(x) = RANDOM(0,1) = 1/2
E[X] = (1/2) * sum (0 to (b-a+1)) 1
= (b-a+1)/2
It seems that the correct answer, I've found on the internet is lg(b-a)
+1
I can sort of see this, because the first time we call random will be
(1/2), second (1/2)*(1/2), etc.. which would
be n calls.. (1/2^n). Can anyone explain further why my answer is
probably wrong, and the lg(b-a)+1 is correct?
Any help is greatly appreciated, Thank You!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
