Ask Question
23 June, 00:43

Find the average number of comparisons to search for a target element x using the sequential search algorithm under the assumption that x is not in the list 80% of the time, but if x is in the list it is equally likely to be at any of the n positions.

+5
Answers (1)
  1. 23 June, 00:49
    0
    0.9n + 0.1, with n the length of the list.

    Step-by-step explanation:

    Lets denote with n the length of the list.

    80% of the time x is not in the list, so 80% of the time we make n comparisons (or we make n comparisons with probability 0.8).

    20% of the time (probability 0.2) we use linear search to find x, since x is equally likely to be at any place on the list, then we should expect that, provivded that x is in the list, we should make (1+2+3+4 + ... + n) / n comparisons (on average). Using Gauss's sum we conclude that the number is equal to (n+1) * n / (2n) = (n+1) / 2 (here we are assuming that x appears only once on the list).

    As a conclussion, the average number of comparisons we make is

    0.8*n + 0.2 * (n+1) / 2 = 0.8n + 0.1n + 0.1 = 0.9n + 0.1

    I hope that works for you!
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Find the average number of comparisons to search for a target element x using the sequential search algorithm under the assumption that x ...” in 📗 Mathematics 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