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?