Chapter 2, Problem 11E

Explanation of Solution

Average case complexity:

The amount of computational resources used by algorithm is averaged by over all  possible inputs is known as average case complexity.

• It is contrasted with worst case complexity which considers maximal complexity of algorithm over each possible inputs.
• Considering access probabilities of all cells in the sequential search procedure, an average value could be calculated.

It is given that:

• Probability of last cell access equals $\frac{1}{2}$ .
• Probability of next to last cell access equals $\frac{1}{4}$.
• Probability of locating number in any of remaining cells is equal to $\frac{1}{4\left(n-2\right)}$.

Calulataion of average case complexity:

The formula for calculation of average case complexity is shown below:

Average case complexity = sum of probabilities of accessing all cells

$\begin{array}{c}Averagecasecomplexity=\frac{1+\mathrm{}}{}\end{array}$