Question

write a recursive algorithm to find the maximum element in an array of n elements and analyze its time efficiency.

(I am using c++ programming language)

Answer 1

#include <iostream>
using namespace std;

// Function to find maximum element in an array of n elements
// i is the current index
// size is the length of array
// arr is the array name
// max is the function name
int max(int arr[], int i, int size){
   // if the i+1 == size is true that means i is the last index of the array
   if(i+1 == size){
      // Then returning element at index i
      return arr[i];
   }
   else{
      // Calculating max for the remaining array starts from index i+1
      int m = max(arr, i+1, size);
      
      // If the max of remaining array is larger than arr[i]
      // Then returning m as the max of the array 
      if(m > arr[i]){
         return m;
      }
      // If the max of remaining array is not larger than arr[i]
      // Then returning arr[i] as the max of the array
      else{
         return arr[i];
      }
   }
}

int main() {
   //Testing
   int arr[] = {4,2,5,1,3,-1};
   int i = 0, size = 6;
   // Making function call to max and printing the returned value to console
   cout<<"Max = "<<max(arr, i, size)<<endl;
   return 0;
}

Base case:
T(1) = 1
Recursive case:
T(n) = T(n-1) + 1
Solving recursive formula:
T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 1 + 1 + 1
     ....
     ....
     = T(n-(n-1)) + 1 + ... + 1 + 1 + 1
     = T(1) + 1 + ... + 1 + 1 + 1
     = 1 + 1 + ... + 1 + 1 + 1
     = n
     = O(n)