Compute average case with best case

Question

is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (n )\right)\implies $ the average case is $\log (n).$

Answer 1

Not at all correct. For example for the naive Quicksort algorithm, anything close to the worst case is very, very, very rare. If the average time was between best and worst case, nobody in their right mind would use Quicksort.

Answer 2

For complexity analysis of some $T(n)$ function we usually consider it's minimum which is worst case, it's maximum, which is worst case, and average. By definition average is expected value of random variable, which means, that we have probability space structure on $T$ domain and, in discrete case, it is defined as

$$ET=\sum\limits_{i} x_i P(T^{-1}(x_i))=\sum\limits_{i} x_i p_i$$

where $x_i$ are values obtained by $T$ and $P(T^{-1}(x_i))=p_i$ is expectation, probability of each $x_i$. So, average is highly dependent on distribituon $(p_1,\cdots,p_n)$.

Now let's consider some examples.

1. Suppose $T$ is constant. Then, obviously min=max=average=$\frac{\text{min}+\text{max}}{2}$.
2. Suppose $T(i)=i$ for $i=\overline{1,n}$. Such complexity we have, for example, for comparisons in simple linear search. Assume, that each value is equally expected with $p_i=P(T^{-1}(i))=\frac{1}{n}$. So called uniform distribution. For average we obtain

$$ET=\sum\limits_{i=1}^{n}\frac{i}{n}=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}=\frac{\text{min}+\text{max}}{2}=\frac{n}{2}+O(1)$$

Now let's consider that probability for value $x_1=T(1)$ is same as for all other values together and is $\frac{1}{2}$. Then we have

$$ET=\frac{1}{2}+\sum\limits_{i=2}^{n}\frac{i}{2n}=\frac{1}{2}+\frac{(n+1)(n-2)}{4n}=\frac{n}{4}+O(1)$$

3. If we consider $T(i)=i^2$ for $i=\overline{1,n}$, then even in uniform distribution case we have

$$ET=\sum\limits_{i=1}^{n}\frac{i^2}{n}=\frac{1}{n}\frac{n(n+1)(2n+1)}{6} = \frac{n^2}{3}+O(1)$$