Basic techniques for design and analysis of algorithms
Edward M. Reingold · ACM Computing Surveys · 1996
It is convenient to classify algorithms based on the relative amount of time they require: how fast does the time required grow as the size of the problem increases?For example, in the case of arrays, the "size of the problem" is ordinarily the number of elements in the array.If the size of the problem is measured by a variable n, we can express the time required as function of n, T(n).When this function T(n) grows rapidly, the algorithm becomes unusable for large n; conversely, when T(n) grows slowly, the algorithm remains useful even when n becomes large.The time required by an algorithm is often analyzed by finding and solving a recurrence relation that describes the time required by the algorithm. AN EXAMPLE: INSERTION SORTHow can we reorder the elements of an array of n values x[1], x[2], . .., x[n] so that they are in perfect order so that x[1] Յ x[2] Յ . . .Յ x[n]?The simplest way to put the values in order is to mimic what we might do by hand: take item after item and insert each one into the proper place among those items already inserted: