The Mathematical Garden

Example: Finding the Maximum Element

Consider the problem of finding the maximum element in an array x[1], x[2], ... , x[n] of distinct numbers. To solve this problem recursively, imagine that given any integer n > 1, you already have a method for obtaining the maximum element in an array of numbers of length less than n. One way to find the maximum element of x[1], x[2], ... , x[n] is as follows:

1. Divide x[1], x[2], ... , x[n] into two subarrays as equal in length as possible;

2. Find the maximum element, maxleft, of the left subarray and the maximum element, maxright, of the right subarray;

3. Compare maxleft and maxright and set the larger equal to the maximum element, maxarray, of the entire array.

Let C_n be the number of comparisons needed to find the maximum of an array of length n, x[1], x[2], ... , x[n], using the approach described above. Therefore we have

Cn = Cën/2 û + Cén/2 ù + 1.

It is clear that C₁ = 0. (Why ?)