Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 69

Algorithm (divide-and-conquer sort)
Input: Array S of n elements; k is global;
Output: Sorted array S of same elements;
void Sort (int S, int n)
{
if (n = k) {
I = n/k;
J = n - I;
//Assume array A consists of first I elements of S.
//Assume array B consists of rest J elements of S.
Sort (A, I);
Sort (B, J);
Merge(A, B, S, I, J); // merge the sorted array A & B into S
}
return;
}
Fig. 3.2
Let T(n) be the worst case time of the divide-and-conquer sort algorithm then we ob-
tain the following recurrence for T

T(n) =

ank

nk n nk f n n k

for

T( / T for

<

+−+ ≥

RS
T )( /)() (3.25)
where a and b are constants and f(n) is the nonrecursive cost function that required to split
the problems into subproblems and/or to merge the solutions of the subproblems into a solu-
tion of the original problem. T(n/k) and T(n – n/k) are the division time that depends upon the
size of the input.

Merge Sort

A procedure merge sort partition the set of elements into two halves (more balanced) and
sorts each halves separately (recursively). Then it merges the sorted halves partitions into
almost equal halves, which requires
n/k ≈ n – n/k
that is only possible when k = 2. Substituting k = 2 in (3.25) the recurrence for T(n), we obtain
the recurrence relation for merge sort,

T(n) =

ank

nnfn nk

for

T( / T for

<

++ ≥

R
S
T 22)(/)()
The presence of floor and selling operators makes this recurrence difficult to interpret.
To overcome this difficulty we assume that n is a power of 2
then ( |n/2| ) = (|n/2|)
Thus, recurrence equation will be

T(n) = RS2T( /annfn+>forfor n=

T

1
21)()
The generation of the recurrence equation (3.26) can be visualized in Fig. 3.3 called
recursion tree. Recursion tree provides a tool for analyzing the cost (time/ other factors) of the
recurrence equation.