Finding the average case complexity for an algorithm?

Question

I'm very lost on finding average case complexity, just pulling a random problem...like.

For a sentinel sequential search, find the average case if the probability is 0 <= p <= 1.

I get the worst case would be O(n+1) as there would be n elements in the array plus the extra element for the key you add on at the end. Best case would be just O(1) if you find it immediately.

I don't really want the answer...but more how...if I just wanted the answer I guess I'd just look a solution manual.

Answer 1

You're right that "average case complexity" requires careful definition of both the algorithm and the set of possible inputs.

The number of comparisons needed to search a linear list of integers provides an example.

If the input search key can be any arbitrary integer, then the average result is that the entire list will be searched (requiring n+1 comparisons to find the sentinel) because there are infinitely many integers and only finitely many elements in the array. Only a finite number of inputs will require less than n+1 comparisons, but infinitely many will cause n+1.

If the analysis on the other hand is the average number of comparisons when the search key is (uniformly) randomly selected from the elements in the array (and those elements contain no repeats), then the average of possible outcomes will be the number of comparisons when the searched-for item is first in the list plus the number when it's second in the list, etc. up to the n'th item, all divided by the number of outcomes, which is n. In other words,

(1 + 2 + ... n) / n = n(n+1)/(2n) = (n + 1) / 2

Here's a sanity check: Let n=1. Then the formula says the average number of comparisons to find the element in the 1-element list is one. That's obviously correct.

A final note is that the way you've posed the questions shows you should study the definition of big-O. O(n) is the same as O(n+1). And big-O is always an expression of an upper bound on whatever's measured. Expressing an upper bound on an average is often not appropriate because the average case analysis normally provides a lower bound as well. The (n+1)/2 comparisons above would best be expressed as \Theta(n) in the average case.