[Algoritmi] Calcolo equazione di complessità

[Lexor]

Ciao, io avrei due semplici equazioni di complessità e non saprei se le ho calcolate correttamente.

La prima:

$T(n) = {(\Theta(1),if n=1),(3T(n/4)+\Theta(n sqrt(n)),if n>=2):}$

Ricavo k da $(1/4)^k n sqrt(n) = 1$ che vale $k = log_4 (n sqrt(n))$, poi trovo che ogni livello equivale a $(3/4)^k n sqrt(n)$.

E trovo la complessità: $\sum_{k=0}^{log_4 (n sqrt(n))} (3/4)^k n sqrt(n) <= n sqrt(n) \sum_{k=0}^{infty} (3/4)^k = n sqrt(n) 1/(1-3/4) = 4 n sqrt(n) = \Theta(n sqrt(n))$


E la seconda:

$T(n) = {(\Theta(1),if n=1),(T(n/4)+T(n/3)+\Theta(n^2),if n>=2):}$

Ogni livello vale $(7/12)^k$, poi studio l'albero con profondità minore $T(n/4)$ e quello massimo $T(n/3)$

Per quello minimo, calcolo $n^2 (1/4)^k rarr k = log_4 n^2$ e risolvo
$\sum_{k=0}^{log_4 n^2} (7/12)^k n^2 <= n^2 \sum_{k=0}^{infty} (7/12)^k = n^2 1/(1-7/12) = \Theta(n^2) rarr T(n) = \Omega(n^2)$

Per il massimo invece calcolo $n^2 (1/3)^k rarr k = log_3 n^2$ e risolvo
$\sum_{k=0}^{log_3 n^2} (7/12)^k n^2 <= n^2 \sum_{k=0}^{infty} (7/12)^k = n^2 1/(1-7/12) = \Theta(n^2) rarr T(n) = \O(n^2)$

Grazie in anticipo

[apatriarca]

Non comprendo il tuo procedimento. Che metodo stai usando? Sembra quello dell'albero ma mi sembra applicato in modo sbagliato.

Per il primo esercizio. Il numero di livelli si ottiene da \(n/4^k = 1 \implies k = \log_4(n). \) Il costo del particolare livello non interviene nel calcolo del numero di livelli. Il costo di ogni livello è anche sbagliato. Il costo si ottiene sostituendo \(n/4^k\) al posto di \(n\) nella parte non ricorsiva. Per il primo esercizio inizio a scrivere \(n \sqrt{n} = n^{3/2}\). Al livello \(k\) avrai quindi che il costo di un singolo nodo è uguale a
\[ \left( \frac{n}{4^k} \right)^{3/2} = \frac{n^{3/2}}{4^{3k/2}} = \frac{n\,\sqrt{n}}{8^k}. \]
Il numero di nodi sarà \(3^k\) per cui il costo totale sarà
\[ 3^k\,\frac{n\,\sqrt{n}}{8^k} = \left(\frac{3}{8}\right)^k \, n\,\sqrt{n}. \]
La complessità finale sarà quindi
\[ \sum_{k=0}^{\log_4(n)} \left(\frac{3}{8}\right)^k \, n\,\sqrt{n} = \frac{1 - (3/8)^{\log_4(n)}}{1 - (3/8)}\,n\,\sqrt{n} < 2\,n\,\sqrt{n} = \Theta(n\,\sqrt{n}). \]

Nel secondo esercizio. Il numero di livelli dei due alberi sono \(\log_4(n)\) e \(\log_3(n)\). In entrambi i casi hai un singolo nodo per ogni livello uguali rispettivamente a \(n^2/16^k\) e \(n^2/9^k\). La somma finale sarà quindi
\[ n^2 \, \Bigg( \bigg(\,\sum_{k=0}^{\log_4 n} (1/16)^k \bigg) + \bigg(\,\sum_{k=0}^{\log_3 n} (1/9)^k \bigg)\Bigg) < 4\,n^2 = \Theta(n^2). \]