Classica ricorrenza

[Giova411]

\(\ T (n) = c + 9T (n/3) \)
Col M. Theorem su degli esercizi trovati in rete indica una complessità \(\Theta(n^2)\)
Non me la spiego ragazzi. Pure, a prima vista, avrei sparato un ordine di grandezza in meno...

[Giova411]

Sempre guessando per i fatti miei....
Ho visto un'altra tipo questa
\(\ T (n) = n + 3T (n/9) \)
Ho detto: \(\Theta(n)\) e poi era giusta....


Buono studio a tutti
grazie

[probid]

Sono uno studente anch'io, ci provo

\(\displaystyle T(n) = 9T(\frac{n}{3}) + c = aT(\frac{n}{b}) + f(n) \)

Primo caso del M.T.: \(\displaystyle \exists \epsilon > 0 : f(n) \in O(n^{log_b(a) - \epsilon}) \implies T(n) \in \Theta(n^{log_b(a)}) \)

\(\displaystyle f(n) = c \in O(1); \; log_b(a) = log_3(9) = 2 \)

Se prendi ad esempio \(\displaystyle \epsilon = 2, \; f(n) \in O(n^{2-\epsilon}) = O(1)\) e dunque \(\displaystyle T(n) \in \Theta(n^2) \)



\(\displaystyle T(n) = 3T(\frac{n}{9}) + n\)

Terzo caso del M.T.: \(\displaystyle \exists \epsilon > 0, \; c < 1 : f(n) \in \Omega(n^{log_b(a) + \epsilon}) \land af(\frac{n}{b}) \leq cf(n) \implies T(n) \in \Theta(f(n)) \)

\(\displaystyle log_b(a) = \frac{1}{3} \)

Prendendo \(\displaystyle \epsilon \in ]0, \frac{2}{3} ]\) e \(\displaystyle c \in [\frac{1}{3}, 1[ \), si ottiene \(\displaystyle T(n) \in \Theta(n) \).

[Giova411]

Sì Grazie, ma non mi sono spiegato rileggendo difatti!!!

Il mio problema è capire ad occhio queste ricorrenze!
Ad esempio trovo difficoltà a prevedere se si possa usare il M T o meno!!!
Sarà che non sono espertissimo...
MI CHIEDO SE CI SIA UN TRUCCO.

La ricorrenza seguente, giusto per mettere carne sul fuoco, come si svolge?

\( \ T (n) = 4T (n/2) + n^2 log n \)

Col M T non si riesce a fare anche se, a prima vista, mi pareva di si...
Facendo Guess esco pazzo poi.......
DITEMI I TRUCCHI DAI