Determinare l'ordine di grandezza del costo in tempo in termini di operazioni aritmetiche della seguente funzione:
- Codice:
int pippo(int n){
int i;
if (n <= 3)
return 1;
else
if(n > 333)
i = n/2;
return 3*pippo(i)+pippo(i)+pippo(i)+n*i;
}
else
return pippo(n-3)+9;
}
dire che l'algoritmo ha tempo d'esecuzione definito da
$ T(n)={ ( O(1)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad n<= 3 ) ,( 3T(n/2)+O(1)\quad\quad n>= 333 ),( T(n-3)+O(1)\quad ):} $
è corretto?
Grazie mile!
