Find the average case complexity of sequential search in an

Find the average case complexity of sequential search in an array ifthe probability of accessing the first cell equals 1/2, the probability of the second cell equals 1/4, and the probability of the third cell equals 1/8. The probability of locating a number in any of the remaining cells is the same for any of these remaining cells.

Solution

for K =1 probabilty is 1/2
for K = 2 probabilty is 1/4
for K = 3 probabilty is 1/8
for K = 4.....n its 1/n-3


We know that the SUm of Probabilities is 1

1 = 1/2 + 1/4 + 1/8 + (n-3)/p
=> (n-3)/p = 1/8
p = 8n-24.


So probability for remaining n-3 elements is 1/8n-24


Now, The average case complexity is given by the expected value of X, which is

E(X) = Summantion of (p*k) where k varies from 1 to n

=> 1*[1/2] + 2*[1/4] + 3*[1/8] + 1/8n-24 * [(n-3)(n-2)/2]

=> 1+ 3/8 + (n²-5n+6)/(8n-24)
=>11/8 + n-4

=> O(N)

Thus the average case time compexity is O(N)