Question

3. Describe a recursive algorithm for finding the maximum element in a array A of n elements. Analyze its time complexity using a recursion tree.

Answer 1

Code:

#include <stdio.h>
int max(int a,int b)
{
    if(a>b)
    {
        return a;
    }
    else
    {
        return b;
    }
}
int find_max(int *a,int n)
{
    int i;
    if(n==1)
    {
        return a[0];
    }
    return max(a[n-1],find_max(a,n-1));
}
int main()
{
    int a[10]={9,10,3,20,5,8,2,1,19,16};
    int b=find_max(a,sizeof(a)/sizeof(a[0]));
    printf("Maximum=%d",b);
    return 0;
}

Screenshots:

Time complexity

T(n) = 1+ T(n-1)

Time complexity = 1+1+1+...... n times = O(n)