Author: Stan Eisenstat
Subject: Re: [Cs223] # of Compares
Date: Tuesday, 03 Mar 2020, 20:19:17

    > Message Posted By: Unknown
    >
    > How do we calculate the average number of compares that a search function
    > takes?

That depends on how average is defined.

If all items are equally likely, then the average is the
sum over the items of the number of compares required to
find it divided by the number of items, or

  (1 + 2 + ... + n) / n = n(n+1)/2 / n = (n+1)/2

--Stan-