Data un'equazione di ricorrenza, ho calcolato l'albero di ricorrenza la cui altezza è $h=log_4n$
Il contributo generale al livello i-esimo è $\sqrt(n)$
Adesso, devo calcolare la somma di tutti i contributi usando la formula
$T(n) = \sum_{i=0}^{h}f(x) $
Dove $f(x)$ è il valore del contributo generale. Facendo le giuste sostituzioni mi ritrovo con:
$T(n) = \sum_{i=0}^{log_4n} \sqrt{n} $
Ora, le mie domande sono su come posso gestire la sommatoria e trovare una soluzione per $T(n)$
So che usando la proprietà distributiva posso portare fuori $\sqrt(n)$ in questo modo
$T(n) = \sqrt{n}\sum_{i=0}^{log_4n} 1 $
Mi chiedo:
1- è corretto mettere 1 nell'ultima sommatoria?
2- se sì, è giusto avere poi questa soluzione? $ \sqrt{n} \cdot (log_4n+1)$
Grazie dell'attenzione