top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+3 votes
125 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 by Mohammed Hussain

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

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 by Sachidananda Sahu
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...