Suppose we carry out a linear (sequential) search of an unordered list L with n

Question

Suppose we carry out a linear (sequential) search of an unordered list L with n items. We are looking for an object X which occurs exactly once in the list, and we start our search from the left of the list. The probability that the object is at any given position is not uniform: Rather it is given by the function Prob.(X is at position i) = (2i /n(n + 1)). Determine the average number of comparisons we must make to find X. (In your analysis here, you may need to make use of the fact that the sums of the squares of the first n natural numbers is n(n + 1)(2n + 1)/6.)

(c) If one were to carry out the linear search described in (b) in reverse order (i.e. starting from the right), determine again the average number of comparisons

Explanation / Answer

Answer::

Avarage number of comparision will be (N+1)/2(N-size of  array).
Because:If elements is in 1st position no of cpmparision will be one and if the element is in the last position then
no of comparisions will be N.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.