Why is p/n in this equation?

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 first 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 first match occurring in the ith position of the list is the same for every i

enter image description here


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.

%d bloggers like this: