Buon pomeriggio a tutti,

Generalmente un equazione di ricorrenza T(n) è descritta come aT(n/b) + D(n) + C(n) dove a sono i sottoproblemi e n/b è la dimensione di ciascun sottoproblemi. Parlando di algoritmi divide-et-impera aT(n/b) rappresenta il tempo impiegato per l'impera, D(n) il tempo impiegato per la procedura Divide e, C(n) il tempo della procedura combina.
Sappiamo che il costo di dividere il problema e combinare i risultati è descritto dalla funzione f(n).

Il primo dubbio è su f(n).

Questa funzione può assumera solamente valore teta(n) o teta(1) no?

Mi spiego meglio.
In caso l'algoritmo sia ad esempio il merge che combina i sottoproblemi prenderà valore teta(n)
nel caso in cui non si presentasse la procedura combina questa prenderebbe sempre il valore teta(1). Sbagliato?