Linear Search Time Complexity Analysis: Part 3


In the previous part we determined the average-case running time of linear search when x, the element we are looking for, appears at least one time in a given array A. In this part, I will show a simpler way to determine the average-case running time.

Instead of thinking about the probability that the first copy of x appears at index i, let’s determine the probability that A[i] will be examined. Let’s denote this event by Ei. Also let’s denote the event that x has been found by Em. Note that the running time is just the number of elements that we have examined.

Let I be the set of indices such that for all i in I: A[i] != x.

Define the random variable Xi over I as follows:
Xi = 1 if Ei occurs, 0 otherwise.

Define the random variable M as follows:
M = 1 if Em occurs, and 0 otherwise.

Note that only one copy of x from A is examined and all other copies must appear after it and so they will never be examined.

And finally, let X by the running time of linear search, then:

X = M + X1 + X2 + … + Xn-k.

Therefore,

E[X] = E[M] + E[X1] + E[X2] + … + E[Xn-k].

We know that E[M] = Pr{M=1} = 1 since k>=1. Now we need to compute E[Xi] or Pr{Xi=1} over I. It is not hard to see that an element that is not x is compared only if it appeared before any of the k copies of x. It’s like asking what’s the probability of choosing that particular element out of the k+1 elements containing k x‘s and one none x? The answer is obvious: 1/(k+1). Now back to the expected running time:

E[X] = 1 + (n-k)/(k+1) = (k+1+n-k)/(k+1) = (n+1)/(k+1). Which is of course the same result we got in Part 2.

Recall that we still have to prove the lemma from Part 2. This turns out be tricky and the next part will be devoted for the proof.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s