Discrete Mathematics for Computer Science

572 CHAPTER 9 Recurrence Relations

9.8.2 Example

Figure 9.5 shows the algorithm applied to an array with eight elements. The recursive calls

to MergeSort are shown in the upper half of the diagram, and the calls to Merge are shown

in the lower half.

31852694

3185 2694

31 85 26 94

3 1 8 5 2 6 9 4

13 58 26 49

1358 2469

123456789

Figure 9.5 Using a merge sort.

9.8.3 Complexity

Let the complexity of MergeSort on an array with n elements be T(n). This function counts

the two kinds of commands that are executed in each call to MergeSort. To complete a call

to MergeSort with an n-element array where n is even requires that MergeSort be executed

twice for arrays of size n/2, followed by the merging of two sorted arrays of size n/2. The

complexity of merging two lists of size n/2 will be proportional to the time that is required

to make at most n comparisons. (See Exercise 7 in Section 1.12.4.) A slight modification of

this argument to handle the case of N being odd leads to the following recurrence relation:

T(n) < T (Ln/2j)+ T (Fn/21)-+tn forn

>1

I forn = 1

This is an upper bound, because you may not require n comparisons to merge the two

lists. (The solution of this recurrence relation will follow as a corollary to the solution of

the recurrence relations that describe the complexity of the class of divide-and-conquer

algorithms presented later.)