Finding the average case running time of linear search
Felipe Vicencio-Heap September 18, 2019
First we restrict the input family to a finite size. Let In = {(L, k) : L = [1, 2, …, n], k ∈ [0, n] ⊂ N} with a uniform distribution. This is a reasonable assumption since we are searching for k, it could appear anywhere in the list, or not at all. The permutations of L have no effect on the running time of linear search, so we do not need to consider them.
We could make weaker assumptions here, but in this case it would not make a difference. We would get a smaller probability for each possible input, and sum over exactly the inverse of that probability, eliminating it as a factor. Try it!
Our assumption that the probability distribution will not necessarily hold in every case, so we should title this “Find the average case running time of linear search given a uniform probability distribution”.
The running time of linear search on input (L,k) is :tn(L,k) = k if 1 ≤ k < n or n + 1 if k = 1. The average case running time of linear search (over In with a uniform probability distribution) is
T′(n)=E[tn]= (tn(L,k)·Pr(L,k)) (L,k)∈In
(1)
tn(L,0) n 1
= n+1 + (tn(L,k)·n+1) (2)
k=1 1 n
=1+n+1· k (3) k=1
= 1 + n(n + 1) ∈ Θ(n) (4) 2(n+1)
1