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 FalseI'm having trouble understanding how he is deriving (n + 1)/2 from the above?
How is this algorithm average case derived?
algorithm analysis;runtime analysis;search algorithms;average case
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$.