2.4 A survey of Common Running Times

When analyzing algorithms,we need to have an approximate sense of the “landscape” of different running times. Most problems have a natural “search space”,which is the set of all possible solutions.When we say we are looking for an efficient algorithm, our goal is actually that of finding algorithms that are faster than the brute-force enumeration of the search space. Thus we always need to think about two bounds when analyzing algorithms: the one on the natural “search space”,which is thus that of the brute-force algorithm for the problem,and the one of the running time we hope to achieve.This section discusses the most common running times of algorithms.