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?