Se la relazione di riccorrenza è diversa vuol dire che è la relazione di ricorrenza di un altro algoritmo.Si ricava proprio da un altro algortimo, che è diverso.
Io ragiono così: prima di tutto assegno un costo a qualsiasi blocco di codice.
Poi mi chiedo quante volte viene eseguito quel blocco in ogni singola chiamata, qual'è la chiamata ricorsiva e qual'è la clausola di chiusura, cioè di temrinazione dell' algoritmo.Rispondendo a queste tre domande so ricavarmi la formula di ricorrenza.
Sempre nell' esempio che ho fatto della f(x), ragiono così:
Assegno un costo c all' istruzione sum+=i;
Rispondo alla rpima domanda: il blocco viene eseguito x volte.
Rispondo alla seconda domanda: la chiamata ricorsiva è f(x/2), per cui al costo di una singola chiamata ci aggiungo questo costo.Rispondo alla terza domanda: l' algoritmo termina quando x=0.
Per cui posso stabilire che il costo è:
- 1 se x=0;
- nc + t(x/2) se x>0.
Ora bisogna calcolare il costo effettivo di una generica chiamata a f(x) passandogli come parametro un valore generico.
Dovrebbe venire (cn^2)/2 se non mi sbaglio.