1.2.3 An Example: Complexity of Mergesort

Mergesort is a divide and conquer algorithm, as outlined below. Note that the function mergesort calls itself recursively. Let us try to determine the time complexity of this algorithm.

list mergesort (list L, int n);

            {

                if (n = = 1)

                    return (L)

                else {

                Split L into two halves L₁ and L₂ ;

                return (merge (mergesort (L₁, ${\frac{n}{2}}$), (mergesort (L₂, ${\frac{n}{2}}$))

                    }

             }

Let T(n) be the running time of Mergesort on an input list of size n. Then,

$$\leq$$ T(n) C₁  (if  n = 1)    (C₁ is a constant)

$$\leq \underbrace{2 \space T \space \left(\frac{n}{2}\right)}_{\mbox{ two recursive \space calls}}^{}\, \underbrace{C_2 n}_{\mbox{cost \space of \space merging}}^{}\,$$

If n = 2^k for some k, it can be shown that 

T(n) $$\leq$$ 2^kT(1) + C₂k2^k That is, T(n) is O(nlog n).
 
 

Figure 1.1: Growth rates of some functions

 
 

Table 1.1: Growth rate of functions

 

	Maximum Problem Size that can be solved in
T(n)	100	1000	10000
	Time Units	Time Units	Time Units
100 n	1	10	100
5 n2	5	14	45
n3/2	7	12	27
2n	8	10	13