Question

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?

Answer 1

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