Prove that T(n) ≤ T(n ′ ) if n ≤ n ′—that is, T is monotonic. hat T(n) ≤ T(n ′ ) if n ≤ n ′—that is, T is monotonic. 6.102 Here is a recurrence relation for the number of comparisons done by mergeSort...

Prove that T(n) ≤ T(n ′ ) if n ≤ n ′—that is, T is monotonic.

hat T(n) ≤ T(n ′ ) if n ≤ n ′—that is, T is monotonic. 6.102 Here is a recurrence relation for the number of comparisons done by mergeSort on an input array of size n (once again, see Figure 6.42):

C(1) = 0 and C(n) = 2C(n/2) + n − 1.

Figure 6.42: The “merging” of two sorted arrays