Ask Question
26 February, 05:15

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?

+3
Answers (1)
  1. 26 February, 07:10
    0
    (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.
Know the Answer?
Not Sure About the Answer?
Get an answer to your 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 ...” in 📙 Computers & Technology if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers