# How is this algorithm average case derived?

For a simple linear search on an unsorted list my textbook says the following:

To determine the average case, you add the number of iterations required to find the target at each possible position and divide the sum by n. Thus, the algorithm performs (n + n - 1 + n -2 + ... + 1)/n, or (n + 1)/2 iterations.

The code example he uses is this:

def sequentialSearch(target, lyst):
"""Returns the position of the target item if found, or -1 otherwise."""
position = 0
while position < len(lyst):
if target == lyst[position]:
return position
position += 1
return False


I'm having trouble understanding how he is deriving (n + 1)/2 from the above?

• Hint: What do you think is the sum of that first expression? Think "Gauss sum". – D.W. Nov 22 '15 at 5:59
• Our reference question may help. You just analyse the algorithm for "find lyst[i]" and average over all i. – Raphael Nov 22 '15 at 9:01

The sum $n+(n-1)+\dots + 3+2+1$ evaluates to $n(n+1)/2$ (it's the so-called Gauss sum). Now divide by $n$, you and get $(n+1)/2$.