GATE CSE
First time here? Checkout the FAQ!
x
0 votes
517 views

Suppose that the probability that x is in a list of n distinct integers is 2/3 and that it is equally likely that x equals any element in the list. Find the average number of comparisons used by the linear search algorithm to find x or to determine that it is not in the list.

asked in Probability by Active (1.6k points) 16 47 71 | 517 views

1 Answer

0 votes
Best answer

$\text{Expected number of comparisons} = \\ \sum_{i=1}^n \left ( \text{number of comparison till }i^{th} \text{ entry}  \\ \times \text{ probability of getting the number at } i^{th} \text{ entry}\right) \\ + \frac{1}{3} . n $

The last $\frac{1}{3} n$ is for the case when $x$ is not in the list.

Probability of $x$ being in the list = 2/3

Since it is equally likely that $x$ is any element in the list, probability that $x$ is element $i$ is $\frac{2}{3n}$

So,

$\text{Expected number of comparisons} = \sum_{i=1}^n \left(i . \frac{2}{3n} \right) +\frac{n}{3} \\= \frac{ n+1}{3} + \frac{n}{3} \\= \frac{2n+1}{3}$

Now, there is a catch here. We have counted one comparison for one element in the linear list. But if we count the loop exit condition and the final found or not check also as in the algorithm give here http://www.programmingsimplified.com/c/source-code/c-program-linear-search, we get $2i + 1$ comparisons for a successful check at $i^{th}$ position and $2n+2$ comparisons if $x$ is not in the list. This would give

$\text{Expected number of comparisons} = \sum_{i=1}^n \left((2i +1) . \frac{2}{3n} \right) +\frac{(2n+2)}{3} \\= \frac{2.( n. (n+1) + n)}{3n} + \frac{2n+2}{3}  \\= \frac{2n+4}{3} + \frac{2n+2}{3}\\= \frac{4n+6}{3}$

answered by Veteran (319k points) 577 1445 2962
selected by
Sir.. you have added 1/3.n for the case when x is not in the list..why so?
1/3 is the probability of x not in the list as given in question.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23386 Points

  2. Bikram

    17068 Points

  3. Habibkhan

    8158 Points

  4. srestha

    6286 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4344 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Ancestor Arijit 2
Good Answer pC
Revival pC
Reader Rajesh R
Reader #Rahul
Popular Question Arnabi
100 Club Rahul68
Popular Question Kanchan kumari
Old-Timer Santanu
Devoted Reader smsubham
27,316 questions
35,170 answers
84,073 comments
33,262 users