(b) Suppose we carry out a linear (sequential) search of an unordered list L wit
ID: 3720406 • Letter: #
Question
(b) 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. We know that there is a higher chance X is in the first half of the list:
Specifically, the probability of finding it in any position i ? n/2 is 2? 2/(n(1 + ? 2)), while the probability for any i > n/2 is 2/(n(1 + ? 2)) (for simplicity - assume n is even). Determine the average number of comparisons we make in this search, for large n (your answer should be a function of
Explanation / Answer
First, consider smaller example...
say list given = {3,1,2} and say you want to search element '2' in sequential way.So first you will visit the first element and compare it with '2'.If it is '2' then your search will end at first element with only 1 comparison. But if it is not equal to '2', then you compare it with the second element. so second element is '1' so again search was unsuccessful and comparison required was total '2' i.e. b/w '2' & '3' and b/w '2' & '1' and so on.
So if the required element is found at first position, no of comparison = 1;
if the required element is found at the second position, no of comparison = 2 ...and so on.
Now since our list is not sorted so it can be anything e.g. list can be {1,2,3} or {3,2,1} or {2,3,1}etc.So the element we are looking for may be present at any of these three positions with equal chances of 1/3.
Now consider our list containing 'n' elements. So element to be searched can be present at any of these 'n' positions in the list with an equal chance(probability) of 1/n.
Total comparison required = No.of comparison if element present in 1st position + No.of comparison if element present in 2nd position + .......+ No.of comparison if element present in nth position
= 1 + 2 + 3+ ......+n = n(n+1)/2
Since there are 'n' elements in the list.
So avg. no. of comparison = Total comparison/total no of elements = [n(n+1)/2] / n = (n+1)/2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.