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.

The running time of these algorithms is at most a constant factor times the size of the input. With these algorithms, the input is typically processed in a single pass, spending a constant amount of time on each item of input enumerated. Examples:

• Computing the Maximum :

algorithm max = a₁ for i = 2 to n:

             if a<sub> i</sub> is greater than max then
                    set max = a<sub> i</sub>
             Endif
        Endfor
        
* Merging Two Sorted lists:

algorithm:

  To merge sorted lists A = a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,...,a<sub>n</sub> and B = b<sub>1</sub>,b<sub>2</sub>,b<sub>3</sub>,...,b<sub>n</sub>:
  Maintain a //current// pointer into each list,initialized to point to the front elements
  While both lists are nonempty:
     Let a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the //current// pointer
     Append the smaller of these two to the output list
     Advance the //current// pointer in the list from which the smaller element was selected
  EndWhile
  Once one list is empty, append the remainder of the other list to the output.