CODEWITHSUNDEEP
pythonalgorithm
flybonzai
flybonzai

Reputation: 3931

Deriving algorithm efficiency on a linear search

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?

Upvotes: 1

Views: 100

Answers (1)

Akshay Hazari
Akshay Hazari

Reputation: 3267

When you iterate over a list to get to the possible target you might take n,n-1,...2,1 attempts to find it. So if you want to find avg case . It will simply be an addition of them all and divided by n. (n+n-1+...+2+1)/n . We know that (n+n-1+...+2+1) = n(n+1)/2 . So we get answer as n(n+1)/2*n which is (n+1)/2 as the avg case.

e.g. for linear search 

 lyst = [4,5,2,1,6]
 possibilities of targets = 4 or 5 or 2 or 1 or 6
 target = 4
 attemps reqd = 1 as found in first attempt i.e first location
 lyst = [4,5,2,1,6]
 target = 5
 attemps reqd = 2 as found in second attempt i.e second location
 lyst = [4,5,2,1,6]
 target = 2
 attemps reqd = 3 as found in third attempt i.e third location
 lyst = [4,5,2,1,6]
 target = 1
 attemps reqd = 4 as found in fourth attempt i.e fourth location
 lyst = [4,5,2,1,6]
 target = 6
 attemps reqd = 5 as found in fifth attempt i.e fifth location

 sum of all attempts reqired = 1 + 2 + 3 + 4 + 5 = 15 
 same as n(n+1)/2 = 5(5+1)/2 = 5*3 = 15

 avg case = (1+2+3+4+5)/n = 15/5 = 3
 same as n(n+1)/2*n = 5(6)/2*5 = (n+1)/2 = 6/2 = 3

Avg means sum of all elements divided by number of elements.

Upvotes: 3

Related Questions