The indepth of Random

generate a bit string using Random(0,1) (the length of the bit string should be ceil (lg(b-a+1)) )...
e.g. random(3,8) means we have to generate a random bit string of length ceil lg 6 which is 3... now if the decimal value of the generated bit string is > 8-3 (i.e if the bit string is either 111, 110) then repeat the procedure... finally return 3 + [decimal val. of generated bit string]...

random(a,b)
{
int dec_val = b-a+1;
while(dec_val > b-a)
{
dec_val = 0;
for j = 1 to ceil(lg(b-a+1))
dec_val = 2*dec_val + random(0,1)
}
return dec_val+a;
}

expected running time calculation: here n is b-a+1

T(n) =
Pr{getting past while loop first time}*lg n
+ Pr{getting past while loop after 2 try}*(2 lg n) + .....

Pr{getting past while loop first time}
= Pr{bit string of length ceil(lg(b-a+1)) has value <= b-a}
= p

now p >= 0.5 (can u see why?)
therefore 0.5 <= p <= 1 and p can be computed but we don't need its value to perform the asymptotic analysis...

T(n) = p(lgn) + (1-p)p(2lg n) + (1-p)^2*p(3 lg n) + .....
= p(lg n)(1 + 2(1-p) + 3(1-p)^2 + 4(1-p)^3 + ... )

now 1 + 1-p + (1-p)^2 + (1-p)^3 + .... = 1/p
differentiating w.r.t p we get 1 + 2(1-p) + 3(1-p)^2 + ... = 1/p^2

therefore T(n) = (lg n)/p

which is O(lg n) or O(lg (b-a+1)) (since 0.5 <= p <= 1, that is p cannot be arbitrarily small)