Use an argument similar to that given in Section 7.9 to prove that log n is a worst-case lower bound for the problem of searching for a given value in a sorted array containing n elements.

Transcribed Image Text:

7.9 Lower Bounds for Sorting This book contains many analyses for algorithms. These analyses generally define the upper and lower bounds for algorithms in their worst and average cases. For most of the algorithms presented so far, analysis is easy. This section considers a more difficult task an analysis for the cost of a problem as opposed to an algorithm. The upper bound for a problem can be defined as the asymptotic cost of the fastest known algorithm. The lower bound defines the best possible efficiency for any algorithm that solves the problem, including algorithms not yet invented. Once the upper and lower bounds for the problem meet, we know that no future algorithm can possibly be (asymptotically) more efficient. A simple estimate for a problem's lower bound can be obtained by measuring the size of the input that must be read and the output that must be written. Certainly no algorithm can be more efficient than the problem's I/O time. From this we see that the sorting problem cannot be solved by any algorithm in less than 2(n) time because it takes at least n steps to read and write the n values to be sorted. Based on our current knowledge of sorting algorithms and the size of the input, we know that the problem of sorting is bounded by f(n) and O(n log n).