[Algoritmi] Ricorrenza con fattore logaritmico

[Leyxargon]

Di nuovo salve a tutti, ho dei problemi con la risoluzione di ricorrenze un po' più "particolari", tipo questa
\begin{equation} \nonumber
T(n)=\begin{cases}
T\left(\frac{3}{8}n\right)+T\left(\frac{5}{8}n\right)+2n\log n & \text{$n\geq 2$}\\
O(1) & \text{$n < 2$}
\end{cases}
\end{equation}

Ho provato ad affrontare il problema mediante l'albero di ricorsione, che mi viene così

Livello 0: $2^0$ nodi = $2n\log n$
Livello 1: $2^1$ nodi
\begin{align*}
= & 2\left(\frac{3}{8}n\right)\log \left(\frac{3}{8}n\right) + 2\left(\frac{5}{8}n\right)\log \left(\frac{5}{8}n\right) \\
= & 2\left[ \frac{3}{8}n (\log 3 + \log n - \log 8) + \frac{5}{8}n (\log 5 + \log n - \log 8) \right] \\
= & 2\left[ \left(\frac{3}{8}n\right)\log 3 + \left(\frac{5}{8}n\right)\log 5 + n\log n - n \log 8 \right] \\
= & 2n\log n - 2n \log 8 + 2n \left( \frac{3}{8} \log 3 + \frac{5}{8} \log 5 \right)
\end{align*}
Livello 2: $2^2$ nodi
\begin{align*}
= & 2\left(\frac{9}{64}n\right)\log \left(\frac{9}{64}n\right) + 4\left(\frac{15}{64}n\right)\log \left(\frac{15}{64}n\right) + 2\left(\frac{25}{64}n\right)\log \left(\frac{25}{64}n\right) \\
= & 2\left[ \frac{9}{64}n (\log 9 + \log n - \log 64) + 2\frac{15}{64}n (\log 15 + \log n - \log 64) + \frac{25}{64}n (\log 25 + \log n - \log 64) \right] \\
= & 2\left[\left(\frac{9}{64}n\right)\log 9 + \left(\frac{15}{32}n\right)\log 15 + \left(\frac{25}{64}n\right)\log 25 + n\log n - n \log 64 \right] \\
= & 2n\log n - 2n \log (8^2) + 2n \left[ \left(\frac{3}{8}\right)^2 \log (3^2) + \left(\frac{5}{8}\right)^2 \log (5^2) + \underline{2\left(\frac{3\cdot 5}{8^2}\right) (\log 3 + \log 5)} \right]
\end{align*}
Arrivato a questo punto ho difficoltà a calcolare la somma dell'i-esimo livello. In particolare non riesco a capire come viene generata la parte sottolineata sopra, ho provato ad azzardare questa soluzione
Livello i: $2^i$ nodi = $2n \log n - 2n \log (8^i) + 2n\{ \left(\frac{3}{8}\right)^i \log (3^i) + \left(\frac{5}{8}\right)^i \log (5^i) + 2\left[\frac{(3\cdot 5)^{i-1}}{8^i}\right] \log [(3\cdot 5)^{i-1}] \}$
Ho forti dubbi sulla correttezza di questo svolgimento, spero che qualcuno possa darmi qualche delucidazione. Grazie!

[Quinzio]

In generale hai le combinazioni date dalla formula binomiale.
Alla generazione $p$ hai le seguenti combinazioni:
$\sum_{k=0}^p (p!)/(k!(p-k)!) a^kb^(p-k)$
Questa specie di grafico ad albero ti fa vedere come si generano.

Codice:

       aaa
   aa
       aab
a
       aab
   ab
      abb
      aab
   ab
      abb
b
      abb
   bb
      bbb


Nel tuo caso
$a = 3/8 n$
$b = 5/8n$

Se la formula che ho scritto sopra la riscriviamo cosi': $\sum_{k=0}^p g(k)$
allora la complessita' che si vuole calcolare sarebbe (alla generazione $p$):
$2\sum_{k=0}^p g(k)\log(g(k))$

Poi siccome bisogna tenere conto di tutte le generazioni
$2\sum_{p=0}^{pg}\sum_{k=0}^p g(k)\log(g(k))$

Come se non bastasse, a complicare ulteriormente le cose c'e' il fatto che
la generazione che scende sotto il 2 "muore" e non genera piu' figli.
Qui pero' non si possono piu' scrivere formule e ci si affida alle stime.

Si puo' ottenere una stima per eccesso calcolando il numero di generazioni massimo
dato dal coefficiente che descresce piu' lentamente (il 5/8 nel tuo esercizio).
O una stima per difetto usando il 3/8.

[Leyxargon]

In generale hai le combinazioni date dalla formula binomiale.
Alla generazione $p$ hai le seguenti combinazioni:
$\sum_{k=0}^p (p!)/(k!(p-k)!) a^kb^(p-k)$
Questa specie di grafico ad albero ti fa vedere come si generano.

Codice:

       aaa
   aa
       aab
a
       aab
   ab
      abb
      aab
   ab
      abb
b
      abb
   bb
      bbb


Nel tuo caso
$a = 3/8 n$
$b = 5/8n$

Se la formula che ho scritto sopra la riscriviamo cosi': $\sum_{k=0}^p g(k)$
allora la complessita' che si vuole calcolare sarebbe (alla generazione $p$):
$2\sum_{k=0}^p g(k)\log(g(k))$

Poi siccome bisogna tenere conto di tutte le generazioni
$2\sum_{p=0}^{pg}\sum_{k=0}^p g(k)\log(g(k))$

Come se non bastasse, a complicare ulteriormente le cose c'e' il fatto che
la generazione che scende sotto il 2 "muore" e non genera piu' figli.
Qui pero' non si possono piu' scrivere formule e ci si affida alle stime.

Si puo' ottenere una stima per eccesso calcolando il numero di generazioni massimo
dato dal coefficiente che descresce piu' lentamente (il 5/8 nel tuo esercizio).
O una stima per difetto usando il 3/8.

Ti ringrazio per il chiarimento. Ammetto di non essere particolarmente ferrato con il calcolo delle sommatorie, quindi vorrei chiederti, volendo fare una stima per difetto dovrei calcolarmi la complessità di $2\sum_{k=0}^{\log_\frac{8}{3}n}g(k)\log (g(k))$? In questo caso come diverrebbe $g(k)$?