Is this code O(n)?

Question

#include <stdlib.h>
#include <time.h>
int maior(int n, int A[]){
    if(n==1)
        return A[0];
    if(maior(n-1, A)<A[n-1])
        return A[n-1];
    else
        return maior(n-1,A);
}
int main(){
    int n, i;
    printf("Tamanho do vetor: ");
    scanf("%d", &n);
    int A[n];
    srand( (unsigned)time(NULL) );
    for(i=0; i<n; i++){
        A[i] = rand();
        printf("%d\n", A[i]);
    }
    printf("O maior valor é: %d", maior(n, A));
}

This code is O(n)?

And it is the best recursive code to search for the highest value within a vector?

Answer 1

No! He has a bug that makes him .

Let’s see the function maior:

int maior(int n, int A[]){
    if(n==1)
        return A[0];
    if(maior(n-1, A)<A[n-1])
        return A[n-1];
    else
        return maior(n-1,A);
}

Note that if n != 1, we call the function maior recursively passing the same array, but as if it had one less element (with the n a smaller unit). If it does not enter the if and fall into the else, the function maior will be called a second time. This means that each call to maior can fire two others and each of them can call two more (totaling four), which in turn can create two more each (totaling eight), etc and will only stop when the n reach 1. That is, grows exponentially.

The solution is to store the value of maior in a variable to call it recursively only once:

int maior(int n, int a[]) {
    if (n == 1) return a[0];
    int m = maior(n - 1, a);
    if (m < a[n - 1])
        return a[n - 1];
    else
        return m;
}

And that can be simplified to that:

int maior(int n, int a[]) {
    if (n == 1) return a[0];
    int m = maior(n - 1, a);
    return m < a[n - 1] ? a[n - 1] : m;
}

These two implementations consist of a recursive call to maior with a few more operations that are in each call. Each call, the size of n decreases by 1 until reaching 1, there will be calls, and then yes that will be .

The for in the main is also, obviously.