Maths/Big O notation

Expectation

After thiswhat you will be able to doCompute the expected comparison count of a front-to-back search from a stated distribution, and show how changing the weights changes the average.

Questionwhat this lesson answersThe average case averages a cost over inputs, but an average has to know how much each input counts. What is that average actually taken over, and why is the weighting a choice you make rather than a fact of the problem?

Not coveredwhat this lesson leaves outWe define the expected value of a cost that takes finitely many values with known weights, and we compute it for one search. We do not prove the laws of probability, and we take the weighting as given rather than arguing for which one is right.

The phrase “average case” can sound as if an algorithm comes with one ready-made ordinary cost. It does not. Consider a search that begins at the front of a list and checks one item after another until it finds the target, the value it was asked to find. This front-to-back examination is a scan. Each check against the target is a comparison. If the target is in position ${k}$, the scan makes ${k}$ comparisons. A target at the front costs one comparison; a target at the end of a list of ${n}$ items costs ${n}$. The algorithm has a different cost for each possible position.

For one fixed list size, each possible comparison count is one possible result. A possible result of this kind is called an outcome. The count changes according to which outcome occurs. A number whose value is selected by an outcome is called a random variable. Here the random variable is the number of comparisons: it can take the values from one through ${n}$. Naming these outcomes does not say how often they happen, so it does not yet give an average.

Decide how much each outcome counts

To form an average, attach a share to every possible position. Each share must be at least zero, at most one, and all the shares together must make one whole. It says how much that outcome counts when we combine the costs. Such a share is called a weight. When the weight is read as a claim about how often an outcome would occur across many searches, it is a probability. The complete list of outcomes together with their weights is called a distribution.

The numbers do not have to be guessed. They may come from a stated model of how requests arrive. Until that model is stated, the arithmetic has no single average to calculate.

This is a choice, not a fact revealed by the scan. Suppose every position receives the same share. An even spread of weights is called uniform, and a distribution with that even spread is a uniform distribution. With ${n}$ positions, each one has weight ${\dfrac{1}{n}}$. That gives the front position no special privilege and the final position no special penalty. It is a clean assumption, but it is still an assumption.

There is now a precise way to combine the costs. Multiply every possible comparison count by its weight, then add the results. An average made by that multiplication-and-addition rule is called a weighted average. For outcomes treated as probabilities, that weighted average is called the expected value, or expectation. Write it with the plain letter ${E}$, for expected value. For the uniform scan, it is

The summing-a-loop lesson obtained the triangular sum by pairing its rows. It gives

Putting that value into the weighted sum gives

Under the uniform choice, the scan therefore makes about half as many comparisons as the worst case:

The average belongs to the assumption too

The result ${\dfrac{n + 1}{2}}$ is not a fact about the scan alone. It is a fact about this scan plus the uniform distribution. The scan has not promised that targets arrive evenly across the list. If a target is almost always near the end, later outcomes receive more weight. Multiplying those larger weights by larger comparison counts moves the expected value toward the worst case. If targets are usually near the front, the same calculation moves the expected value in the other direction.

Nothing in the code changed. The possible outcomes remained the same numbers, and the cost of an outcome remained its position. Only the distribution changed. That is why “average case” is meaningless until the weighting is named. Saying merely that a cost is average hides the part that decides what is being averaged over.

The expected cost is still a function of ${n}$. Under the uniform assumption it is ${\dfrac{n + 1}{2}}$, which grows in step with ${n}$, a linear term. It can therefore be classified with ${O}$, ${\Omega}$, and ${\Theta}$ in exactly the same way as any other cost function, using the machinery the earlier O(f) lesson built. Classifying it does not turn the chosen distribution into a universal truth.

An average can also conceal a bad outcome. A rare case can contribute little to the weighted sum while still being unacceptable when it occurs, and then the comfortable typical result is the wrong summary. Placing this weighted average beside the smallest and largest costs for the same algorithm, so the three finally come apart, is what the doors below lead to.