Average time of sequential search in unordered array

Example

Sequential search on an unordered array.

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

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 search

(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)

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

Average-case running time for unsuccessful search

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

(Because for linear search, it's the worst case each time it's unsuccessful.)

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

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

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

Mathematica can't  nicely simplify the above formula to a polynomial    A×n + B =
                         (1-(q/2))n + (q/2) 
for n. 

As an exercise, let's pretend that we can't do it, eaither.

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

0<1-(q/2)<∞

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

More precisely,

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

meaning

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

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

Simplify[%]

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

Optimality

Theorem

For an unordered array, sequential search is average-case optimal in the class C of algorithms that search by comparison of keys.

Proof. 

1.Unsuccessful sequential search on an unordered array is average-case optimal in class C. 

The lowewr bound on the  number of comparisons is n. 

This can be established by means of adversary strategy explained in the proof of optimality of sequential search in the worst case (file  WorstTimeSeqSearch.nb).

But n is also the number that unsuccessful sequential search performs.

Hence the optimality of unsuccessful sequential search in class C.

2. Successful sequential search on an unordered array is average-case optimal in class C.

Regardless of the order in which x is compared to the elements of array I, any search that serches an unordered array by comparisons of keys can be forced (by an adversary strategy) for each 
0 ≤ i < n 
and some array I,to perform i+1 or more comparisons, each with probability of (1/n).

(Exercise: Design such an adversary strategy. Hint: Begin for an adversary strategy that forces the search in question to perform n or more comparisons similar to one described in the proof of optimality of sequential search in the worst case (file  WorstTimeSeqSearch.nb). Then use it to find the required adversary strategy.)

This demonstrates that the formula

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

provides a lower bound for average number of comparisons while searching an unordered array of n elements.

But the above formula also provides  the average number of comparisons sequential search will perform while searching an unordered array of n elements.

Hence the average-case optimality of sequential search on an unordered array.

Since both unsuccessful and successful sequential search of an unordered array are average-case optimal in class C, the sequential search of an unordered array is optimal in class C, too.                                                     □