This code is O (n)?

Navigation

#1 by (8 votes)

2

#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 is it the best recursive code to look for the highest value within a vector?

c

asked by anonymous 10.01.2018 / 16:47

1 answer

8

No! It has a bug that causes it to be $O(2^n)$ .

Let'sseethemaiorfunction:

intmaior(intn,intA[]){if(n==1)returnA[0];if(maior(n-1,A)<A[n-1])returnA[n-1];elsereturnmaior(n-1,A);}

Notethatifn!=1,wecallthefunctionmaiorrecursivelypassingthesamearray,butasifithadonelesselement(withnasmallerunit).Ifitdoesnotenterifandfallintoelse,themaiorfunctionwillbecalledasecondtime.Thismeansthateachcalltomaiorcantriggertwoothersandeachofthemcancalltwomore(totalingfour),whichinturncancreatetwomoreeach(totalingeight),etcandwillonlystopwhenntoreach1.Thatis,itgrowsexponentially.

Thesolutionistostorethevalueofmaiorinavariabletocallitrecursivelyonlyonce:

intmaior(intn,inta[]){if(n==1)returna[0];intm=maior(n-1,a);if(m<a[n-1])returna[n-1];elsereturnm;}

Andthiscanbesimplifiedtothis:

intmaior(intn,inta[]){if(n==1)returna[0];intm=maior(n-1,a);returnm<a[n-1]?a[n-1]:m;}

Thesetwoimplementationsconsistofarecursivecalltomaiorwithsomemoreoperationsthatare on each call. Since with each call, the size of n decreases by 1 until it reaches 1, there will be $n$ calls, and then yes it will be $O(n)$ .

The for in main is $O(n)$ also, of course.

10.01.2018 / 17:03

Find out which div with the same class is larger Regular expression to find numbers in the middle of words