Originariamente inviato da gabama
Buonasera,mi sono trovato a ragionare su questi 2 algoritmi e vorrei delle conferme,se possibile,sulla complessità

codice:
int fun(int a[], int n) {
  int i;
  if(n<2) return a[0];
  for(i=1;i<n;i++)
    a[i] = a[i]-a[i-1];
  return fun(a,1) + fun(a,n-1);
}
sarebbe O(1)+O(n) = O(n)
è semplicemente così o dimentico qualcosa?
Dimentichi sì qualcosa: tu esegui la chiamata ricorsiva di questa funzione ~n volte su un input ogni volta più piccolo di una unità (per ognuna di queste chiamate in realtà esegui anche un'altra chiamata fun(a,1), ma la possiamo trascurare perché il suo tempo di calcolo è costante e quindi essendo ripetuta n volte ha complessità O(n) che è asintoticamente trascurabile nel nostro caso).
Di conseguenza abbiamo una sommatoria per i da 1 a n di {O(i) (=fun(a,n-1)) + O(1) (=fun(a,1)) }
Quindi T(n) = O(n^2) + O(n) = O(n^2)
Tutto questo l'ho fatto al volo e spero di non aver detto ca**ate, quindi prendetelo con il beneficio del dubbio.

EDIT: in teoria si dovrebbe risolvere una semplice equazione di ricorrenza per calcolare T(n) ma ho evitato perché trovo che così spiegato sia più intuitivo.