Apriorna slozenost rekurzivne funkcije

[danielvast]

Ej ljudi mala pomoć ako itko zna koja je apriorna složenost rekurzivne funkcije npr:

Code:

int fib(int n){
    if(n<=1) return 1;
    return fib(n-1)+fib(n-2);
}

2^n ili n^2.
Unaprijed hvala

[schmrz]

O(n^2) :)

Mada nisam 100% siguran. Znao sam nekada tačno analizirati algoritme, gledao sam neka predavanja sa MIT-a ako se ne varam pa ih možeš potražiti. Ali je to bilo podavno, a nije mi trebalo i onda se tako zaboravi...

[kecko]

slažem se sa schmrzom n^2 je jer se u n puta poziva 2X fib()...

[danielvast]

OK hvala vam velika !!