A primary goal of this handbook is to guide a reader with a specific problem to the most appropriate data structure(s) and the most appropriate algorithm(s) for a particular application. Generally, the most important criteria in this selection process is the efficiency, in time and space, of the solution. Therefore, a natural question arises: How does one measure the efficiency of an algorithm or data structure method? As a simple example, we consider the problem of sorting a collection of n comparable elements. The algorithm’s execution time depends on many things, including:
• The hardware on which the algorithm will be executed. • The compiler used create the executable. • The size of the input (i.e., n = 1000 versus n = 1, 000, 000). • The form of the input itself. For example, if insertion sort is given an input that is nearly
sorted, it runs very quickly, yet it runs much more slowly on an input in reverse sorted order.