Question

The following pseudocode finds the maximum element in an array of size n.

Int MAX (int A [ ], int n) { M = A[0]; for i = 1 to n – 1     if (A[i] > M)         M = A[i]        //Update the max return M; }

1. Write a recursive version of this program.

2. Let f(n) be the number of key comparisons performed by this algorithm. Write a recurrence equation for f(n).

3. Prove by induction that the solution of the recurrence is f(n) = n − 1.

Answer 1

Recursive version of this program:

Approach:

1. We have to Recursively traverse the array from the end,
2. Base case: If the remaining array is of length 1, then we have to return the only present element i.e. arr[0]

   if(n == 1)
      return arr[0];

3. Recursive call: If the base case is not satisfied, then we will call the function by passing the array of one size less from the end, i.e. from arr[0] to arr[n-1].
4. Return statement: At each recursive call (except for the base case), we have to return the maximum of the last element of the current array (i.e. arr[n-1]) and the element returned from the previous recursive call.

   return max(arr[n-1], recursive_function(arr, n-1));
   

Pseudocode:

Int MAX (int A [ ], int n) {
  if (n == 1) 
      return A[0]
  
  if(A[n-1] > MAX(A, n-1))
      return A[n-1]
  else
      return MAX(A, n-1)
}

Now, let f(n) be the number of key comparisons performed by this algorithm, then from the above recursive algorithm, f(n) = f(n - 1) + 1

Here, 1 denotes 1 key comparisons happening in base case.

Now, solving f(n), given f(n) = 1 (base case)

f(n) = f(n-1) + 1

f(n-1) = f(n-2) + 1

...

...

f(2) = f(1) + 1

Here, adding RHS and LHS, f(n) = f(1) + n - 2 = n - 1

Therefore f(n) = n - 1

Now, proving this using Induction:

Base Case: f(n) = 1

Assume for n = k, this function is satisfied: f(k) = k - 1

Now, Proving it for n = k + 1

f(k + 1) = k + 1 - 1 = k

So, true for n = k + 1

Hence, the expression is true,                                             PROVED