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?

Read more here: https://stackoverflow.com/questions/64835818/why-is-p-n-in-this-equation

### Content Attribution

This content was originally published by MaskerTim at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.