Establishing a lower bound for searching
Today, we are going to establish a lower bound for searching and prove that binary search is optimal, and no comparison based search in this universe would be better than that by more than a constant factor. Let’s define our problem more formally first. Theorem Let us assume that we have n pre-processed items in the array. Finding a given item among them in a comparison model requires Ω(log2n) in the worst case. Computation Model Let’s try to model the situation using a decision tree. In this decision tree, an internal node represents a decision that our algorithm makes and a leaf represents an answer. Here’s our representation of the problem using a decision tree computation model for n=3 element array for the sake of simplicity. I mentioned here that the Items are preprocessed to mean you could do whatever you want with items ahead of time. For instance, I can sort them, build them into an AVL tree et.al. Proof Let n be the number of items in the input array. Then, w...