4
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ How could an upper bound for the worst case not be an upper bound for the average case? $\endgroup$ – A.Schulz Oct 20 '14 at 5:38
9
$\begingroup$

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))$

$\endgroup$
  • 1
    $\begingroup$ Great answer! You can also check Decision-tree-Model, to visually figure out the complexity of the algorithm (Reference: CLR) $\endgroup$ – user3378649 Oct 19 '14 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.