Why is p/n in this equation?

Question

In the book Introduction to the Design and Analysis of Algorithms, it provides pseudocode of this algorithm and analyzes average efficiency of this:

ALGORITHM SequentialSearch(A[0..n − 1], K)
  //Searches for a given value in a given array by sequential   search 
  //Input: An array A[0..n − 1] and a search key K
  //Output: The index of the ﬁrst element in A that matches K
  // or −1 if there are no matching elements
  i ← 0
  while i < n and A[i] != K do
    i ← i + 1
  if i < n return i
  else return −1

And then this is average-case efficiency it analyzes and takes some assumption as below:

the probability of a successful search is equal to p (0 ≤ p ≤ 1).
the probability of the ﬁrst match occurring in the ith position of the list is the same for every i

why is it p/n there?

user_1328439 · Answer

If the probability to encounter K at each position using the SequentialSearch were uniformly equal to p/n this would be a rather strange assumption as this would mean that the probability for K to actually occur at each position is not uniformly distributed.

Indeed, if K occurs multiple times in the array only the first occurrence will ever be found by SequentialSearch, so the values of K located further to the end of the array would never play a role in the complexity calculation. If we let K occur multiple times in the array the relative weight of the earlier occurrences must be higher and thus the probability to terminate early must be higher than the probability to find the first occurrence of K at the last location.

Yet as we will later find out in many introductory textbooks this algorithm is analyzed under an assumption that the first slot where we encounter K in the array may occur in any location of the array with equal probability. Likely this is because the formulas are slightly easier to derive. But hold on.

To the contrary in non-textbook complexity analysis of array algorithms we assume that each slot in the array is an independent variable with the same probability to take any admissible value. In Probability Theory such sequence of independent random variables obeying the same probability distribution is often referred to as Bernoulli trials.

Analysis with independent random variables

Suppose each slot in the array may independently take the value of K with equal probability q. Then the probability of a successful search can be computed with the Bernoulli formula for n independent trials. It gives:

$\Sigma_{k>0} \left(\begin{array}{c}n \ k\end{array} ight) q^k (1-q)^{n-k} = 1 - (1-q)^n = p$

This means that

So p is only approximately equal to q * n and approximation error grows quickly with n.

In the case of Bernoulli trials the formula for the average complexity can be written as follows:

$C_{ extrm{avg}} = q [ 1 + 2 (1-q) + \ldots + n (1-q)^{n-1} ] + n (1-q)^n$

Using the formula for the sum of arithmetic-geometric progression and substituting 1-p for (1 - q)^n we can simplify this expression:

$[ \begin{split} C_{ extrm{avg}} = q [ 1 + 2 (1-q) + \ldots + n (1-q)^{n-1} ] + n (1-q)^n\ = \frac{q}{1-q} [ (1-q) + 2(1-q)^2 + \ldots + n(1-q)^n] + n (1-q)^n \ = \frac{1}{q} [1 - (1-q)^n - nq(1-q)^n] + n (1-q)^n \ = \frac{1}{q} [p - nq(1-p)] + n (1-p) \end{split} ]$

The resulting formula looks different from the formula in textbook.

Now we can try to experimentally check which formula is correct. Below is a plot of the results and the Python code used to generate the data for the plot. The parameters N_SIZES, N_TRIES, and STEP were changed from the ones used for the plot to get the results faster.

import csv 
import numpy as np

def generate_array(arr_size, max_value):
    random = np.random.randint(max_value, size=arr_size)
    return list(random)

def sequential_search(data_array, value_to_search):
    found = False
    try:
        result = data_array.index(value_to_search)
        found = True
    except ValueError:
        result = len(data_array)
    return found, result

def write_results(sizes, c_avg, p_avg):
    with open(f'cavg_{N_SIZES}_{N_TRIES}_{N_RANGE}.csv', 'w') as csvfile:
        csv.writer(csvfile).writerows(zip(sizes, c_avg, p_avg))

N_TRIES = 100 
N_SIZES = 1000
N_RANGE = 200
STEP = 10

def main():
    c_avg = []  # array to hold the average number of comparisons
    p_avg = []  # array to hold the frequency of success
    sizes = []  # array to hold array sizes

    for array_size in range(1, N_SIZES, STEP):
        value_to_search = np.random.randint(1, N_RANGE)
        success_rate = 0 
        c_avg_value = 0 
        for _tries in range(N_TRIES):
            arr = generate_array(array_size, N_RANGE)
            found, result = sequential_search(arr, value_to_search)
            if found:
                success_rate += 1
            c_avg_value += ((result * 1.0)/N_TRIES)
        c_avg.append(c_avg_value)
        p_avg.append((success_rate * 1.0)/N_TRIES)
    sizes.append(array_size)

    write_results(sizes, c_avg, p_avg)

if __name__ == '__main__':
    main()

To conclude. I would say that the analysis in this textbook is not correct under the assumption of independent equally distributed values in the array. But this is not the full story.

When the formula from the textbook becomes correct

However there is a case when the analysis from the textbook stands. Suppose we have M distinct entities. We can identify them with the numbers 0 to M-1. And we have n slots, and n < M. Now we randomly assign entities to slots so that M-n entities remain unassigned. Now given a number K we want to check if this number has been assigned a slot.

The probability of success here would be p = n/M and the values in the slots are now dependent: If slot 1 is assigned the value a then slot 2 can only hold a value b that is different from a, and slot 3 can only hold a value c that is different from both a and b, and so on.

The chance of finding K in the first slot is 1/M that is equal to p/n. Now the chance of finding K by Sequential Search in the second slot is also equal to 1/M=p/n. This seems obvious if you think about it.

To convince us that this is correct let us use the formula for conditional probability:

$[ \begin{align} P( ext{$K$ in slot 2}) & = P( ext{$K$ not in slot 1}) \cdot P( ext{$K$ in slot 2} | ext{$K$ not in slot 1}) \ & = \left(1 - \frac{1}{M} ight)\cdot \left(\frac{1}{M-1} ight)\ & = 1/M \end{align} ]$

We can prove by induction that P(K in slot j) = 1/M holds for every j from 1 to n.

So we can compute the average complexity of SequentialSearch using the formula from the textbook.

The Introduction to the Design and Analysis of Algorithms textbook cites Computer Algorithms: Introduction to Design and Analysis by Van Gelder and Baase where they arrive to the same formula without any calculations at all. They just say: if we search an array of length n, the average length of search would be (n+1)/2 so the average case complexity is

$C_{ extrm{avg}}= p(n+\frac{1}{2}) + (1-p) n$

This textbook however specifically highlights the assumption that all elements in the array are distinct and thus not independent.

An example

If you find the formulas hard to follow probably there is nothing better to illustrate the difference between the two cases then an example.

Let the range of possible values M = 3, the length of the array n = 2 and K = 1.

In the case of independent values we have the following 9 possibilities

Independent values
11       21       31
12       22       32
13       23       33

And we can compute the average complexity of SequentialSearch as

$C_{ extrm avg} = \frac{1}{9}(1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2) = 1\frac{2}{3}$

Now p = 5/9 and q = 1/3 so the new formula gives

$C_{ extrm avg} = \frac{1}{q} [p - nq(1-p)] + n (1-p) = 3 [\frac{5}{9} - 2\cdot \frac{1}{3}\cdot \frac{4}{9}] + 2\cdot\frac{4}{9} = 1\frac{2}{3}$

And the textbook formula gives

$C_{ extrm avg} = p\frac{n+1}{2} + (1-p)n = \frac{5}{9}\cdot\frac{3}{2} + \frac{4}{9}\cdot 2 = \frac{31}{18}$

In the case of distinct values we have only 6 possibilities

distinct values
12       13       23
21       31       32

So p = 2/3 and C_avg = 1/6 * (1 + 2 + 1 + 2 + 2 + 2) = 1 2/3.

Here the textbook formula is correct:

$C_{ extrm avg} = p\frac{n+1}{2} + (1-p)n = \frac{2}{3}\cdot\frac{3}{2} + \frac{1}{3}\cdot 2 = 1\frac{2}{3}$

It may be surprising that the average complexity was the same both under the assumption of distinct values and with independent values, and a coincidence it is. In general this does not hold. For instance, consider the case of M = 3, n = 3, K = 1. In this case with independent values we get p = 19/27 and C_avg = 2 1/9 and with distinct values p=1 and C_avg = 2.

Conclusion

Now it is up to you to decide whether the formula in the textbook is the correct solution for the average complexity of the algorithm or not:

if you believe that the values in the array are independent, then you need the new formula,
if the values are all distinct, then you need the formula from the textbook.

* Formulas rendered with QuickLaTeX

user_1400793 · Answer

Each of the n locations have the same probability of being the first match, and the probability that K occurs anywhere is p. So each location must have probability p/n of being the first match.

You could also write the first line as:

C_avg(n) = p(1/n + 2/n + 3/n + ... + n/n) + (1-p)n

This, in my opinion, separates the two cases (K is found vs not found) more obviously.

Why is p/n in this equation?

2 Answers

Analysis with independent random variables

When the formula from the textbook becomes correct

An example

Conclusion