[ASD]Risoluzione equazione di ricorrenza - metodo iterativo

[HackAlli]

Salve

Sono ancora io e adesso sono alle prese con quest' altra relazione
\(T(n) = 3T(\lfloor \frac{n}{4} \rfloor) + \theta(n^2) \)
e facendo i vari passaggi iterativi trovo la formula generale che dovrebbe essere questa:
\(T(\frac{n}{4^i}) = 3^iT(\lfloor \frac{n}{4^i} \rfloor ) + n^2 \sum_{j=0}^{i-1} (\frac{3}{16})^j \)
essendo \( (\lfloor \frac{n}{4^i} \rfloor) == 1\) quando \( i = \lg_4 n \) allora:
\(T(n) = 3^{\lg_4 n} + n^2 \sum_{j=0}^{\lg_4 (n)-1} (\frac{3}{16})^j =\)
\( = 3^{\lg_4 n} + n^2[-\frac{16}{13}((\frac{3}{16})^{\lg_4 n} - 1)] = O(n^2)\)

Sinceramente \( O(n^2) \) l'ho messo un pò a caso poichè non so confrontare la complessità di tempo dell'intera espressione.
Ho provato con il metodo dell'esperto ,ma con scarsi risultati dato che non ho capito bene come applicarlo e per questo mi appello a voi su come riuscire a verificare tale risultato e se questo proposto da me sia giusto.

[apatriarca]

Inizio per prima cosa dal Master Theorem. La relazione è certamente nella forma corretta, con \(a = 3,\) \(b = 4\) e \(f(n) \in \Theta(n^2) \). Siccome \(2 > \log_b a = \log_4(3) = 0.7924812503605781 \) ci troviamo nel caso \(3\) e quindi la complessità totale è \(\Theta(n^2)\). Non ho controllato i tuoi calcoli, ma direi che a grandi linee dovrebbe essere così..