Asked By : Conor
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32090
Answered By : InformedA
- 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 $sumlimits_{i=1}^{log(n)} frac{i2^{i-1}}{n} = frac{1}{n} sumlimits_{i=1}^{log(n)} i2^{i-1}$ Now you can do integration on an approximation formula which will give you $O(nlog(n))$. Note that $intlimits_{1}^{log(n)} x 2^x dx$ can be calculated and bounded into $log(n)*2^{log(n)} = nlog(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} sumlimits_{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))$
