Questo esercizio chiede di calcolare la complessità in funzione di n dell’istruzione
y=g(f(n)) con le seguenti definizioni di funzione.
Indicare le eventuali relazioni di ricorrenza e spiegare brevemente il calcolo della complessità dei cicli.
int g(int x) {
if (x<=1) return 10;
int b=0;
for (int i=1; i<=x*x; i++)
b+=i;
return b+g(x/2)+g(x/2);
}
int f(int x) {
if (x<=1) return 1;
int a=0; int b=0;
for (int i=1; i<= g(x); i++)
a++;
cout >> f(x-1)+a;
return a;
}
La soluzione per
g(n) dice: