Ask 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?

+3
Answers (1)
  1. 2 February, 20:05
    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?
Find 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 the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers