Average time of sequential search in ordered array

Example

Sequential search on an ordered array.

Find an item x in an ordered array I based only on comparisons of x to elements of I.

I[0] ≤ I[1] ≤ I[2] ≤ ... ≤ I[k - 1] ≤ I[k] ≤ ... ≤ I[n - 1]
   
Notation   

size (I) - number of elements to be searched.
   
   T (n) - 
 number of comparisons performed while searching of an entry in an n - 
 element array I.
   
   Average - case running time for successful sequential search (same as for an unordered array, which we have already done)

(Subscript[T, avg]^succ)(n) = (∑_(i=0)^(n-1))Pr((Subscript[I, i])| success)*t((Subscript[I, i])) =

(∑_(i=0)^(n-1))(1/n)(i+1)

Note. For sequential search, (Subscript[T, avg]^succ)(n)is the same for ordered and unordered array because sequential search does not take advantage of the order while successfully searching for a key.

For unsuccessful sequential search, there are n+1 possible outcomes

x < I[0] - it results in 1 comparison

I[0]<x<I[1] - it results in 2 comparisons

...

I[i-1]<x<I[i] - it results in i+1 comparisons

...

I[n-2]<x<I[n-1] - it results in n comparisons

I[n-1]<x - it results in n comparisons


Let's assume that all these outcomes are equally likely, that is, all have the probability (1/(n+1)).

(Subscript[T, avg]^fail)(n) =

((∑_(i=0)^(n-1))(1/(n+1))(i+1)) + (1/(n+1))n

Hence,(Subscript[T, avg])(n)=q*(Subscript[T, avg]^succ)(n)+p*(Subscript[T, avg]^fail)(n)=

=q*(1+n)/2+(1-q)*((n/2)+(n/(1+n)))=

q*(1+n)/2+(1-q)*((n/2)+(n/(1+n)))

Simplify[%]

((3 n+(n^2)+q-n q)/(2+2 n))

Limit[(((3 n+(n^2)+q-n q)/(2+2 n))/n),n -> ∞]

0<(1/2)<∞

So, (Subscript[T, avg])(n)∈Θ(n)

More precisely,

 (Subscript[T, avg])(n)~ (1/2)n

meaning

 (Subscript[T, avg])(n)=(1/2)n + o(n)

Note that the above charactgerizations are independent of probabilities p and q.

Optimality

For an ordered array, sequential search is NOT average-case optimal. For instance, binary search performs less comparisons on an average than sequential search does.

This part it optional
Begin of optional part

((3 n+(n^2)+q-n q)/(2+2 n))-(1/2)n

Simplify[-(n/2)+((3 n+(n^2)+q-n q)/(2+2 n))]

Limit[((2 n+q-n q)/(2+2 n)),{n-> ∞}]

{1-(q/2)}

((3 n+(n^2)+q-n q)/(2+2 n))-(1/2)n-(1-(q/2))

Simplify[-1-(n/2)+(q/2)+((3 n+(n^2)+q-n q)/(2+2 n))]

Thus

(Subscript[T, avg])(n)=(1/2)n + 1-(q/2) + o(1)

End of optional part