Analyze the following randomized binary search procedure for the expected runnin

Question

Analyze the following randomized binary search procedure for the expected running time. Give an exact expression for the expected running time (number of comparisions) if you can, for the cases x in the array (may also need to fix the rank) and x not in the array. To use this function we will call RandomizedBinarySearch(A, 1, n, x). Assume that the function RAND(a,b) called below for integers a < b, generates an integer uniformly at random in the range [a, b].

Data: Array A 1 nl of distinct numbers (sorted), indexes lo, hi, and number ac Result The index i E o, hi such that Ali r or -1 n hi lo 1; if n 0 then return -1 if m 1 and Allo then return lo else if n 1 then return -1; r RAND(lo, h if Ar r then return r else if Arl z then. return RandomizedBinarySearch (A, r 1, hi, z); else return RandomizedBinarySearch(A, lo, r 1, r); Algorithm 1: RandomizedBinary Search (A, lo, hi, a)

Explanation / Answer

Solution:

Let's start discussing from line to line about running time of the algorithm named RandomizedBinarySearch(A, lo, hi, x)

n= hi-lo+1, so here one addition one subtraction and an assignment operation is performed which will take constant amount of time, i.e O(1).

Now here only one comparison is done which will also take constant amount of time, i.e. O(1)

next line will also take O(1) time

now here two comparison has been done which is considered as O(1) time

next line will also take O(1) time

next line one comparison O(1) time

similarly next four lines will take O(1) time, considering RAND function will also take O(1) time

Now here RandomizedBinarySearch is called recursively, either RandomizedBinarySearch(A, r+1, hi, x)

or RandomizedBinarySearch(A, lo, r-1, x)

So these two function will search for the element x and in the process they will divide the array into two halves but those two halves are not divided linearly from in between it's completely random, so in worst case scenario the algorithm will take O(n) time.

and recurrence will be T(n)= T(n/2)+c

on average case the complexity will be O(log n).

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.