How to analyze/test a binary search algorithm?

Problem Detail: 

I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log n)? And the average would be something like n + n/2 + n/4... etc?

I'm then asked to "Implement a program performing an empirical test of the binary search (using a fixed number of random arrays for each n), then do a ratio test justifying your analytical answer." How would I go about doing this? Could I perform a basic binary search algorithm on a number of random arrays, counting the basic operations, and compare that to my original analysis from the first question?

I appreciate any help/guidance here.

Asked By : Jakemmarsh

Answered By : Yuval Filmus

First, of all, the worst-case running time of binary search is $\Theta(\log n)$. What you are looking for is the average running time of binary search under some reasonable random model, for example the element to be looked for is chosen uniformly at random from the (distinct) elements in the array.

Second, the average running time can't be $n + n/2 + n/4 + \cdots$, since the average running time is lower than the worst-case running time. I'm not sure what exactly you're counting here. The average running time is the average number of operations taken by your algorithm, on a random input. In contrast, the worst-case running time is the maximal number of operations taken by your algorithm on any input.

Perhaps the following example will make things clear. Consider the following task: given an array of size $2n$ containing $n$ zeros and $n$ ones, find the index of a zero. The worst-case running time of any algorithm is $\Omega(n)$. In contrast, consider the algorithm which scans the array from left to right, and returns the first zero index. Its worst-case running time is $\Theta(n)$. Under the assumptions that the input array is chosen randomly among all legal arrays, the average running time is $\Theta(1)$ (why?). You can modify the algorithm to one which probes locations randomly, and then the worst-case expected running time is $\Theta(1)$. (If you don't understand the last remark, wait until you learn about randomized algorithms.)

Finally, you're required to empirically demonstrate the claimed average running time $\Theta(f(n))$. The idea is that for large $n$, the average running time will be $\approx C f(n)$ for some constant $C$ whose units are seconds. In other words, $C$ is the constant "hidden" inside the big O notation. Suppose you calculate for several values of $n$ an average $T(n)$ over several runs of the algorithms. Then you expect $T(n)/f(n)$ to be roughly constant, and that would demonstrate your claim concerning the average running time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16057