algorithm - Expected number of updates to find approximate minimum using the following algo -

consider following code:

public int find_exponent(array) {     int count = 0;     double min = epsilon;     (int i=0; i<array.length; i++) {       if (array[i] < min) {         count++;         min = min/2;       }     }     return count; } 

suppose input array of length n , randomly generated(and entries iid , ranges [0, 1]) unknown density f. expected value of count ? understand underlying density unknown it's not possible explicit solution want solution in terms of f (or corresponding cdf: f) , initial guess min i.e epsilon.

note: i'm not interested find exact minimum in given array

you can approach problem following way.

first off, suppose type of min meant float/double since array array has values in range [0, 1]. now, define f

f(x) = p(x <= x) 

i.e cumulative density function , g(i, c) probability after i-th iteration have count == c

you can see that:

g(x, c) = p(x >= eps/2^c)*g(x, c) + p(x <= eps/2^(c-1))*g(x, c-1) = (1-f(eps/2^c))*g(x, c) + f(eps/2^(c-1))*g(x, c-1) 

notice since g(0, 0)=1 can calculate g(x, c), 0<=x<=n, 0<=c<=n bottom-up approach.

here first couple of values of g:

g(0, 0) = 1  g(1, 0) = 1-f(e) g(1, 1) = f(e)  g(2, 0) = (1-f(e))^2 g(2, 1) = f(e)(1-f(e)) + f(e)(1-f(e/2)) g(2, 2) = f(e)f(e/2) 

the expected count be:

e[count] = 0*g(n,0)+1*g(n,1)+...+n*g(n,n)