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?

  • 1
    $\begingroup$ Hint: What do you think is the sum of that first expression? Think "Gauss sum". $\endgroup$ – D.W. Nov 22 '15 at 5:59
  • $\begingroup$ Our reference question may help. You just analyse the algorithm for "find lyst[i]" and average over all i. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.