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.
 

To show that this algorithm spends a constant amount of time on each element:

        Suppose the cost of each iteration  is charged to each element that is selected and added to the list \\
        An element can be charged only once,since at the moment it is first charged,it is added to the output and never seen by the algorithm.\\
        But there are only 2//n// elements in  total and the charge of each iteration is accounted for by a charge of some element\\
        Thus there can be only 2//n// iterations \\
        Each iteration takes a constant amount of time,so the in total, the algorithm takes O(//n//)\\

• O(nlogn) Time

It's the running time of any algorithm that splits the input into two equal-sized pieces,solves each piece recursively and then combines the two solutions in linear time.