edited by
31,316 views
55 votes
55 votes

The average number of key comparisons required for a successful search for sequential search on $n$ items is

  1. $\frac{n}{2}$
  2. $\frac{n-1}{2}$
  3. $\frac{n+1}{2}$
  4. None of the above
edited by

8 Answers

Best answer
110 votes
110 votes
Expected number of comparisons
$= 1 \times$ Probability of first element being $x + 2 \times$ Probability of second element being $x + \ldots  +n  \times$ Probability of last element being $x$.

$= \frac{1}{n} + \frac{2}{n} + \frac{3}{n} +\ldots +\frac{n}{n} $

$ = \frac{\left ( \frac{n\times (n+1)}{2} \right ) } {n} $

$ = \frac{n+1}{2}$

Correct Answer: $C$
edited by
71 votes
71 votes
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 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 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 required element is found at first position , no of comparison = 1;
if required element is found at 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 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.
6 votes
6 votes
Searching an element in an array, the search starts from the first element till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.
4 votes
4 votes

For our array, the element to be searched sequentially gives the following possibilities:

If our element is present in the $1^{st}$ index itself: Total no. of comparisons=1

If our element is present in the $2^{nd}$ index of array: Total no. of comparisons=2

If our element is present in the $3^{rd}$ index of array: Total no. of comparisons=3

.

.

.

If our element is present in the $n^{th}$ index of array: Total no. of comparisons=n

Average number of comparisons=$\frac{1+2+3+.....n}{n} =\frac{n(n+1)}{2*n}=\frac{n+1}{2}$

Answer:

Related questions

35 votes
35 votes
6 answers
1
Kathleen asked Oct 9, 2014
12,511 views
Relative mode of addressing is most relevant to writing:Co – routinesPosition – independent codeShareable codeInterrupt Handlers
21 votes
21 votes
7 answers
3
Kathleen asked Oct 4, 2014
18,308 views
Algorithm design technique used in quicksort algorithm is?Dynamic programmingBacktrackingDivide and conquerGreedy method
33 votes
33 votes
5 answers
4