CODEWITHSUNDEEP
algorithmrandomtimebinary-search
S.Dan
S.Dan

Reputation: 1912

Expected running time of randomized binary search

I want to calculate the expected running time of randomized binary search of the following pseudo-code, where instead of considering the midpoint as the pivot, a random point is selected:

BinarySearch(x, A, start, end)
    if(start == end)
        if(A[end] == x) 
            return end
        else
            return -1
    else
        mid = RANDOM(start, end)
        if(A[mid] == x)
            return mid
        else if(A[mid] > x)
            return BinarySearch(x, A, start, mid-1)
        else
            return BinarySearch(x, A, mid+1, end)

I looked at this previous question, which has the following:

T(n) = sum ( T(r)*Pr(search space becomes r) ) + O(1) = sum ( T(r) )/n + O(1)

How is this obtained? 

sum( T(r)*Pr(search space becomes r) )

And in the last line of calculation, how was this obtained? 

T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n)

Upvotes: 0

Views: 1406

Answers (2)

mkon
mkon

Reputation: 1

I would argue that the recurrence only holds when the target element is the first/last element of the array. Assume that the target element is in the middle, then in the first call we reduce the size of the array to be up to n/2, not n as in the recursion. Moreover, the position of the target element may change with each recursive call. For the proof of O(log n) complexity you may want to see my answer which uses another approach here.

Upvotes: 0

Yola
Yola

Reputation: 19019

sum( T(r)*Pr(search space becomes r) )

This line obtained by observing fact that you can choose any point to partition array, so to get expected time you need to sum up all possiblities multiplied with their probabilities. See expected value.

T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n)

About this line. Well you can think of it as of integral of 1/x on [1, n] and it is log(n) - log(1) = log(n). See Harmonic series.

Upvotes: 1

Related Questions