3.2. Analyzing Search in Unsorted Lists¶
3.2.1. Analyzing Search in Unsorted Lists¶
You already know the simplest form of search: the sequential search algorithm. Sequential search on an unsorted list requires \(\Theta(n)\) time in the worst case.
How many comparisons does linear search do on average? A major consideration is whether \(K\) is in list L at all. We can simplify our analysis by ignoring everything about the input except the position of \(K\) if it is found in L. Thus, we have \(n+1\) distinct possible events: That \(K\) is in one of positions 0 to \(n-1\) in L (each position having its own probability), or that it is not in \(L\) at all. We can express the probability that \(K\) is not in L as
where \(\mathbf{P}(x)\) is the probability of event \(x\).
Let \(p_i\) be the probability that \(K\) is in position \(i\) of L (indexed from 0 to \(n-1\). For any position \(i\) in the list, we must look at \(i+1\) records to reach it. So we say that the cost when \(K\) is in position \(i\) is \(i+1\). When \(K\) is not in L, sequential search will require \(n\) comparisons. Let \(p_n\) be the probability that \(K\) is not in L. Then the average cost \(\mathbf{T}(n)\) will be
What happens to the equation if we assume all the \(p_i\) ‘s are equal (except \(p_n\))?
Depending on the value of \(p_n\), \(\frac{n+1}{2} \leq \mathbf{T}(n) \leq n\).
3.2.1.1. Lower Bounds Proofs¶
Given an (unsorted) list L of \(n\) elements and a search key \(K\), we seek to identify one element in L which has key value \(k\), if any exists. For the rest of this discussion, we will assume that the key values for the elements in L are unique, that the set of all possible keys is totally ordered (that is, the operations \(<\), \(=\), and \(>\) are defined for all pairs of key values), and that comparison is our only way to find the relative ordering of two keys. Our goal is to solve the problem using the minimum number of comparisons.
Given this definition for searching, we can easily come up with the standard sequential search algorithm, and we can also see that the lower bound for this problem is “obviously” \(n\) comparisons. (Keep in mind that the key \(K\) might not actually appear in the list.) However, lower bounds proofs are a bit slippery, and it is instructive to see how they can go wrong.
Here is our first attempt at proving the theorem.
Is this proof correct? Hopefully it is reasonably obvious to you that not all algorithms must search through the list in a specific order, so not all algorithms have to look at position L [\(n\)] last.
OK, so we can try to dress up the proof by making the process a bit more flexible.
Is this proof correct? Still, no. First of all, any given algorithm need not necessarily consistently skip any given position \(i\) in its \(n-1\) searches. For example, it is not necessary that all algorithms search the list from left to right. It is not even necessary that all algorithms search the same \(n-1\) positions first each time through the list. Perhaps it picks them at random.
Again, we can try to dress up the proof as follows.
Unfortunately, there is another error that needs to be fixed. It is not true that all algorithms for solving the problem must work by comparing elements of L against \(K\). An algorithm might make useful progress by comparing elements of L against each other. For example, if we compare two elements of L, then compare the greater against \(K\) and find that this element is less than \(K\), we know that the other element is also less than \(K\). It seems intuitively obvious that such comparisons won’t actually lead to a faster algorithm, but how do we know for sure? We somehow need to generalize the proof to account for this approach.
We will now present a useful abstraction for expressing the state of knowledge for the value relationships among a set of objects. A total order defines relationships within a collection of objects such that for every pair of objects, one is greater than the other. A partially ordered set or poset is a set on which only a partial order is defined. That is, there can be pairs of elements for which we cannot decide which is “greater”. For our purpose here, the partial order is the state of our current knowledge about the objects, such that zero or more of the order relations between pairs of elements are known. We can represent this knowledge by drawing directed acyclic graphs (DAGs) showing the known relationships, as illustrated by the following slideshow.
