Proving that the average case complexity of binary search is O(log n)

Question

I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go about proving that the average case complexity of binary search is O(log n)?

Answer 1

I think most text book will provide you a good proof.

For me, I can show the average case complexity as follows.

Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$.

• For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case
• For the case of 2 reads, one will read the middle position and then 1 of the 2 other middle positions from the 2 sub-arrays. This probability is $\frac{2}{n}$

• For the case of 3 reads, there are $2*2$ positions which result in this cost as you go into the 4 sub-arrays of the first 2 sub-arrays. The probability for this cost is $\frac{2^2}{n}$

  ...

• For the case of $x$ reads, the probability for this case is $\frac{2^{x-1}}{n}$

For the average case, the number of reads will be

$\sum\limits_{i=1}^{\log(n)} \frac{i2^{i-1}}{n} = \frac{1}{n} \sum\limits_{i=1}^{\log(n)} i2^{i-1}$

Now you can do integration on an approximation formula which will give you $O(n\log(n))$. Note that $\int\limits_{1}^{\log(n)} x 2^x dx$ can be calculated and bounded into $\log(n)*2^{\log(n)} = n\log(n)$ This is a very good way to do that applies to many cases.

Another way to see it can also be $i2^{i-1} < \log(n) * 2^{i-1}$

Then the formula above is bounded by $\frac{\log(n)}{n} \sum\limits_{i=1}^{\log(n)} 2^{i-1}$

The summation part is actually $\frac{1 - 2^{\log(n)}}{1 - 2} = 2^{\log(n)} - 1 = n - 1$ which is definitely less than $n$, multiplying this with $\frac{\log(n)}{n}$ gives you what you want $\log(n)$

So you will get the bound as you want $O(\log(n))$