Question

Using Sequential Search on an array of size n, the search key is definitely present in the array. The probability of matching the key to the nth item in the array is 1/3, and the probability of matching the key to the (n-1)st item is 1/2. The probabilities of matching each of the remaining items are all equal. What is the average case complexity function for Sequential Search under these conditions?

Answer 1

Answer:

(11n-5) / 12 is correct answer.

Explanation:

The Probability that key will match to nth term = 1/2

The Probability that key will match to n-1th term = 1/3

As all other probabilities are equal

The Total Probability that key matches to any of 1 to n-2 index = 1 - 1/2 - 1/3 = 1/6

The Probability that key matches to any of 1 to n-2 index = (1/6) / n-2 = (1/6)* (n-2))

Let P(i) = Probability that key matches to ith index.

The Average time complexity = 22 i=1 P(i) * i

The Average time complexity = 1/(6(n-2) * ( sum of 1 to n-2 ) + (n-1) / 3 + n/2

The Average time complexity = 1/(6(n-2) * ( n-2)*(n-1) / 2 + ( n-1) / 3 + n/2

The Average time complexity = 1/6 * (n-1)/2 + (n-1)/3 + n/2

The Average time complexity = (n-1)/12 + (n-1)/3 + n/2

The Average time complexity = (n-1 + 4 * n - 4 * 1 +6 * n)/12

The Average time complexity = 11n-5 / 12

so (11n-5) / 12 is correct answer.