Chapter 5, Problem 1R

Explanation of Solution

Recursive method to find the maximum element in array:

The recursive method to find the maximum element in array “A” of “n” elements is given below:

The findMax() method returns the maximum elements in array.

//Define the findMax() method

public static int findMax(int[] a, int n)

{

  //Check whether the "n" is equal to "1"

  if (n == 1)

  //Return the maximum element

  return a[0];

/*Call the max() method and recursively call findMax() method*/

return max(finMax(a, n - 1), a[n - 1]);

}

The max() method returns the maximum elements by comparing the array elements.

//Define the max() method

private static int max(int n1, int n2)

{

/*Check the "n1" is greater than "n2". If yes, return the maximum element. */

  return n1 > n2 ? n1 : n2;

}

Explanation:

In the above code,

• Check whether the “n” element is equal to “1”. If yes,
  • It return the array of “a[0]”. That is, first element is a maximum element in given array “a”.
• Call the max() method to compare the array elements by calling the findMax() method recursively to find and return the maximum array element.

Running time:

The running time of above code is given below:

According this code,

• The basic operation is comparison. That is, comparing the array elements recursively to find the maximum element in array.
• If there is no comparison. Then, the maximum array element is “a[0]” is “1”.
• Compare array value until “n-1” by calling the findMax() method. Then,

  $\begin{array}{l}\text{a}\left(\text{n}\right)\text{ = n-1+1}\hfill \\ \text{ =}\text{n}\hfill \end{array}$

• Then, the array value is “a[n]” is “n”.
• Thus, it will recursively call the findMax() method to perform the “n” time of execution for “n” inputs. So, the usage space and time for this “n” array is $\text{O}\left(\text{n}\right)$.

Therefore, the running time and space of maximum element in array is $\text{O}\left(\text{n}\right)$.