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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.