Mathematical Foundation of Computer Science

DHARM

70 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

From the recursion tree shown in Fig. 3.3, we observe that size as a function of node
depth is given n/2, n/4, n/8, ...... n/2d for depth 1, 2, 3, ...... d (respectively). Thus, the base case
occur about at d = log (n). Since, sum of each row is n (total for the tree), therefore, recursion
tree evaluation obtains the value T(n) is about n log (n).
Latter, in this section we will see that the solution of this recurrence obtains using
fundamental methods is θ(n log n).

T(n) n

T(n/2) n/2 T(n/2) n/2

T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/4) n/4

Fig. 3.3 Recursion tree.

Chip-and-Conquer
Let the main problem of size n can be ‘chipped-down’ to subproblems of size s and (n-s) (s > 0),
with nonrecursive cost f(n) (to split out the problem into subproblems and/or to combine the
solution of subproblems into a solution to main problem).
Then the recurrence equation is,
T(n) = T(s) + T(n – s) + f(n) for s > 0 (3.27)
Quick Sort
Quick sort strategy is to rearrange the elements to be sorted such that all small elements
come first to large elements in the array. Then quick sort sorts the two subranges of small
and large keys recursively with the result that entire array is sorted. Quick sort algorithm is
shown in Fig. 3.4.
Algorithm (Quick Sort)
Input: Array S of n elements;
Output: Sorted array S of same elements;

Select an element from array S[0:n-1]for middle;

Partition the remaining elements into two segment left and right, s.t.

All elements in left have lesser than that of middle and

All elements in right have larger than middle.

Sort left with quick sort recursively.

Sort right with quick sort recursively.

Result is left followed by middle followed by right.

Fig. 3.4