Average linear search algorithm runtime

Question

I am trying to get the average runtime for a deterministic linear search algorithm. The algorithm searches for element x in an unsorted array A in the order of A [1], A [2], A [3] ... A [n]. It stops when it finds the element x or continues until it reaches the end of the array. I searched wikipedia and the answer was (n + 1) / (k + 1), where k is the number of times x present in the array. I approached differently and received a different answer. Can someone please give me the correct proof and also let me know what happened to my method?

E(T)= 1*P(1) + 2*P(2) + 3*P(3) ....+ n*P(n) where P(i) is the probability that the algorithm runs for 'i' time (ie compares 'i' elements). P(i)= (ni)C(k-1) * (nk)! / n! Here, (ni)C(k-1) is (ni) Choose (k-1). As the algorithm has reached the ith step, the rest of k-1 x must be in the last ni elements. Hence (ni)C(ki). (nk)! is the total number of ways of arranging the rest non x numbers, and n! is the total number of ways of arranging the n elements in the array. 

I do not get (n + 1) / (k + 1) in simplification.

Answer 1

You forgot to account for permutations of k copies of x . The correct definition of P(i) is

 P(i) = (ni)C(k-1) * k! * (nk)! / n! = (ni)C(k-1) / nCk. ^^ 

I will go to Mathematica:

 In[1]:= FullSimplify[Sum[i Binomial[ni, k-1]/Binomial[n, k], {i, 1, n}], 0 <= k <= n] 1 + n Out[1]= ----- 1 + k 

---

To elaborate on my comment below: suppose that all elements are different, let X be a set of matches, and Y a set of inconsistencies. By assumption | X | = k and | Y | = nk. The expected number of readings is equal to the sum over the elements e of the probability of reading e.

Given the many elements of S, each element of S comes before everyone else with a probability of 1 / | S |.

An element x in X is read if and only if it occurs before every other element of X, which is a 1 / k probability. The total contribution of elements to X is | X | (1 / k) = 1.

An element y in Y is read if and only if it comes before each element from X, which is the probability 1 / (k + 1). The total contribution of elements to Y is | Y | (1 / (k + 1)) = (nk) / (k + 1).

We have 1 + (nk) / (k + 1) = (n + 1) / (k + 1).

Answer 2

Here is a solution that uses the terms Cormen: Let S be the set of other nk elements.
Let the indicator random variable Xi=1 , if we meet the element i'th from the set S during our execution.
Pr{Xi=1}=1/(k+1) and, therefore, E[Xi]=1/(k+1) .
Let the indicator random variable Y=1 if we encounter any element k that we are looking for in the course of our execution.
Pr{Y=1}=1 and, therefore, E[Y]=1 .
Let the random variable X=Y+X1+X2+...X(nk) be the sum of the elements that we encounter during our execution.
E[X]=E[Y+X1+X2+...X(nk)]=E[Y]+E[X1]+E[X2]+...E[X(nk)]=1+(nk)/(k+1)=(n+1)/(k+1) .