CODEWITHSUNDEEP
algorithmbig-otime-complexitybinary-search
thenewbrocks
thenewbrocks

Reputation: 1

Binary search with Random element

I know that Binary Search has time complexity of O(logn) to search for an element in a sorted array. But let's say if instead of selecting the middle element, we select a random element, how would it impact the time complexity. Will it still be O(logn) or will it be something else?

For example : A traditional binary search in an array of size 18 , will go down like 18 -> 9 -> 4 ...

My modified binary search pings a random element and decides to remove the right part or left part based on the value.

Upvotes: 0

Views: 1874

Answers (3)

mkon
mkon

Reputation: 1

The recursion in the answer of @Yves Daoust relies on the assumption that the target element is located either at the beginning or the end of the array. In general, where the element lies in the array changes after each recursive call making it difficult to write and solve the recursion. Here is another solution that proves O(log n) bound on the expected number of recursive calls.

Let T be the (random) number of elements checked by the randomized version of binary search. We can write T=sum I{element i is checked} where we sum over i from 1 to n and I{element i is checked} is an indicator variable. Our goal is to asymptotically bound E[T]=sum Pr{element i is checked}. For the algorithm to check element i it must be the case that this element is selected uniformly at random from the array of size at least |j-i|+1 where j is the index of the element that we are searching for. This is because arrays of smaller size simply won't contain the element under index i while the element under index j is always contained in the array during each recursive call. Thus, the probability that the algorithm checks the element at index i is at most 1/(|j-i|+1). In fact, with a bit more effort one can show that this probability is exactly equal to 1/(|j-i|+1). Thus, we have

E[T]=sum Pr{element i is checked} <= sum_i 1/(|j-i|+1)=O(log n),

where the last equation follows from the summation of harmonic series.

Upvotes: 0

user1196549
user1196549

Reputation:

My attempt:

let C(N) be the average number of comparisons required by a search among N elements. For simplicity, we assume that the algorithm only terminates when there is a single element left (no early termination on strict equality with the key).

As the pivot value is chosen at random, the probabilities of the remaining sizes are uniform and we can write the recurrence

C(N) = 1 + 1/N.Sum(1<=i<=N:C(i))

Then

N.C(N) - (N-1).C(N-1) = 1 + C(N)

and

C(N) - C(N-1) = 1 / (N-1)

The solution of this recurrence is the Harmonic series, hence the behavior is indeed logarithmic.

C(N) ~ Ln(N-1) + Gamma

Note that this is the natural logarithm, which is better than the base 2 logarithm by a factor 1.44 !

My bet is that adding the early termination test would further improve the log basis (and keep the log behavior), but at the same time double the number of comparisons, so that globally it would be worse in terms of comparisons.

Upvotes: 2

Simba
Simba

Reputation: 1651

Let us assume we have a tree of size 18. The number I am looking for is in the 1st spot. In the worst case, I always randomly pick the highest number, (18->17->16...). Effectively only eliminating one element in every iteration. So it become a linear search: O(n) time

Upvotes: 1

Related Questions