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.
