Copyright by Dr. Marek A. Suchenek 2012,2013,2014
This material is intended for future publication.
Absolutely positively no copying no printing no sharing no distributing of ANY kind, please.

Average-case lower bound on searching for x in a sorted array E with n elements

Results:

Theorem 1.

The average number of comparisons of keys that any algorithm to search an ordered array must perform is at least

(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q

where q is the probability of success.

Theorem 2.

Binary Search is average-case optimal in the class C of search algorithms  search an ordered array by comparisons of keys.

I will prove Theorem 2. This, and the derived (already done) average number of comaprisons of keys performed by Binary Seach will prove Theorem 1.


Input: array E of n elements;
		key x.

Output: and index i s.t. 
x = E[i] 
if found (successful search);
otherwise (unsuccessful search)
a pair of idicies -∞:0 if x < E[0]
or
a pair of idices i:i+1 if E[i]<x < E[i+1]
or
a pair of idices n-1:∞ if x > E[n-1]

Note: We do not need assumption n = (2^k)-1 here.

Asserted even probability distribution:

All successful search outcomes are equally likely
and
all unsuccessful search outcomes are equally likely.

(A case of uneven probability distribution will be tackled in Chapter 10 Section 4.)

The result is proven for any algorithm that searches via decision tree; in particular, for any algorithm that searches by comparisons of keys.



Example decision tree T for searching (reused from Binary Search); nodes represent indicies (success) or pairs of indicies (failure) in array E:

TreePlot[{5->2,5->8,2->1,2->4,8->7,8->10,0->"-∞:0",1->0,3->"2:3",4-> 3,6->"5:6",7->6,10->9,10->"10:∞",0-> "0:1",1-> "1:2",3-> "3:4",4-> "4:5",6-> "6:7",7-> "7:8",9-> "8:9",9-> "9:10"},VertexLabeling->True,DirectedEdges->True,VertexRenderingFunction->({White,EdgeForm[Black],Disk[#,.3],Black,Text[#2,#1]}&),AspectRatio->0.55]

External nodes are green.  These are non-decision nodes that represent the final outcomes of unsuccessful searches.
All others are decision nodes or the final outcomes of successful searches.

Comment. The optimality proof presented here makes use of the fact (demonstrated in class) that the decision tree TB for Binary Search on N nodes has the  minimal internal path length and the minimal external path length.

1. Successful search

p- the length of a path to an internal node in T

p+1-the number of comparisons done along a path to an internal node in T

N - the number of decision nodes in the decision tree (N = 11 on the above picture)

ipl(T) - the sum of lengths of all paths to internal nodes in T

ipl(T)+N - the sum of numbers of comparisons done along all paths to internal nodes in T

The minimal internal path length (the concept of ipl was covered in Data Structures class) in
 any binary tree T with N nodes is (Subscript[ipl, min])(N).

Fact (((Subscript[ipl, min])(N))/N) is a growing function.
Exercise: Prove it!

DiscretePlot[(∑_(i=1)^n)((⌊Log2[i]⌋)/n),{n,2,200}]

We have:

(Subscript[T, avg]^succ)(N) =((ipl(T))/N)+1≥(((Subscript[ipl, min])(N))/N) +1≥(((Subscript[ipl, min])(n))/n) +1=(Subscript[BS, avg]^succ)(n),
where (Subscript[BS, avg]^succ)(n)is the average number of comparisons of keys performed by successful Binary Search, as it has been calculated in file
http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageTimeBinSearch.nb
Thus Binary Search is average-case optimal in the case of successful search.

2. Unsuccessful search

p- the length of a path to an external node in T

p-the number of comparisons done along a path to an external node in T

N+1 - the number of non-decision nodes in the decision tree (N+1 = 12 on the above picture)

epl(T) - the sum of lengths of all paths to external nodes in T

epl(T) - the sum of numbers of comparisons done along all paths to internal nodes in T

The minimal external path length (the concept of ipl was covered in Data Structures class) in
 any binary tree T with N nodes is (Subscript[epl, min])(N).

Fact (((Subscript[epl, min])(N))/(N+1)) is a growing function.
Exercise: Prove it!

DiscretePlot[(((∑_(i=1)^n)⌊Log2[i]⌋+2n)/(n+1)),{n,2,200}]

We have

(Subscript[T, avg]^fail)(N) =((epl(T))/(N+1))≥ (((Subscript[epl, min])(N))/(N+1))≥ (((Subscript[epl, min])(n))/(n+1))=(Subscript[BS, avg]^fail)(N),
where (Subscript[BS, avg]^fail)(n)is the average number of comparisons of keys performed by unsuccessful Binary Search, as it has been calculated in file
http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageTimeBinSearch.nb
Thus Binary Search is average-case optimal in the case of unsuccessful search.

Therefore, Binary Search is average case optimal.

In particular, every algorithm that searches an element in an ordered array must perform, on average, at least as many comparisons of keys as the Binary Search does.

The rest of this file is optional for all students.

More precise low and high approximations 
for N ≥ 1000

Plot[Tooltip[{(((N+1))/N) (Log2[N+1]+ϵ[N+1])-1,Log2[N+1]+ϵ[N+1],Log2[N],Log2[N]-1,Log2[N]+.085,Log2[N]-.915}],{N,1000,10000}]

Here is a graph of the difference 
(Subscript[T, avg]^fail)(N)-(Subscript[T, avg]^succ)(N); it converges to 1 as N diverges to ∞.

Plot[{Log2[N+1]+ϵ[N+1] - 
 ((((N+1))/N) (Log2[N+1]+ϵ[N+1])-1),1}, {N, 1, 400}]

Here is the limit in ∞ of the difference:

Limit[Log2[N+1]+ϵ[N+1] - 
 ((((N+1))/N) (Log2[N+1]+ϵ[N+1])-1), N-> ∞]

Note. Although the difference between the total number of comparisons in unsuccessful search and the total number of comparisons of successfull search in any search algorithm that searches an N-element sorted array by means of decision tree is exactly N, the difference between the respective averages is not exactly 1. This is due to the fact that the successful average is given by the successful total divided by N and the unsuccessful average is given by the unsuccessful total divided by 
N+1 . If N is large then the ratio of (N/(N+1))is close to 1, and the difference between these averages is close to 1 as well.

Theorem 1.

The average number of comparisons of keys that any algorithm to search an ordered array must perform is at least

(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q ≈

≈Log2[n+1]+ϵ[n+1] -q.

Proof.  

(Subscript[T, avg])(N)=q×(Subscript[T, avg]^succ)(N)+(1-q)×(Subscript[T, avg]^fail)(N)=

q(((n+1)/n)(Log2[n+1]+ϵ[n+1])-1) +(1-q)(Log2[n+1]+ϵ[n+1])=

=(q((n+1)/n)+(1-q))(Log2[n+1]+ϵ[n+1]) -q=

=(q(((n+1)/n)-1)+1)(Log2[n+1]+ϵ[n+1]) -q=

=(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q≈

≈Log2[n+1]+ϵ[n+1]-q.

Now the combined average, in 3D with second parameter q (probability of success)

Plot3D[(1+(q/N))(Log2[N+1]+ϵ[N+1]) -q,{N,1,20},{q,0,1}]

Theorem 2.

The average number of comparisons of keys that binary search performs is

(1+(q/n))(Log2[n+1]+ϵ[n+1]) -q ≈

≈Log2[n+1]+ϵ[n+1] -q.

Proof completes one in file CSC401/Website/Mathematica/AverageTimeBinSearch.nb. 

Binary Search is optimal because its decision tree has all external nodes on one level or on two adjacent levels and, therefore, is a shortest possible decision tree with at least n decision nodes. So, it must have the same average as the derived lower bound.

We will elaborate more on this subject in Chapter 4.