   # What is the average number of comparisons needed in a sequential search ....?

+3 votes
132 views

What is the average number of comparisons needed in a sequential search to determine that the element is not there, if the elements are completely unordered? posted Aug 17, 2015
Share this question

## 1 Answer

0 votes

To calculate average number of comparison needed in sequential search =
Average of the time/comparison required in all the cases where positions of the key element may be present at any place + key element is not present

So if you see total number of cases = N + 1

N + 1 Cases
Time required to search if key element is present at 1st position( Θ(1) ) + Time required to search if key element is present at 2nd position( Θ(2) ) +
Time required to search if key element is present at 3rd position ( Θ(3) ) + ........................ + Time required to search if key element is present at Nth position ( Θ(n) )+ Time required to search if key element is not present( Θ(n) )

So average = (Time required for all N + 1 cases) / (N + 1 )

In an N sized array key element ma present at any of the n places or may not be present

so Average time = (Θ(1) + Θ(2) + Θ(3) + Θ(4) + ...................... + Θ(n) + Θ(n) ) / (N + 1)

so average time/comparison = [(Θ(N * (N + 1) / 2) + Θ(n) )] / (N + 1 )

Correct me if i am wrong answer Aug 18, 2015
Similar Questions
+3 votes

Input:
[1 7 15 29 11 9]

Output:
[9 15] [1 7 11 29]

Average of first part: (15+9)/2 = 12,
Average of second part: (1 + 7 + 11 + 29) / 4 = 12