[Algoritmi] Equazione di ricorrenza

[rubotubo]

Come posso trovare la soluzione della seguente equazione di ricorrenza? È possibile usare il Teorema_principale ?
\(\displaystyle T(1) = c \)
\(\displaystyle T(n) = 7T(\frac{n}{2})+18(\frac{n}{2})^2 \)

[apatriarca]

La struttura dell'equazione di ricorrenza è certamente quella che viene presa in considerazione nel teorema principale. Per capire se è possibile fare uso di tale teorema è quindi sufficiente vedere se la tua equazione rientra in uno dei tre casi. Si vede subito che abbiamo \( f(n) = \frac{9}{2}\,n^2 = \Theta(n^2) \). Abbiamo inoltre che \(a = 7\) e \(b = 2\).

1. Per il primo caso vogliamo trovare se esiste una costante \(\epsilon > 0\) per cui \( f(n) = O(n^{\log_b a - \epsilon}). \) Siccome \(\log_b a \approx 2.8\) la condizione è certamente verificata. Per cui abbiamo che \(T(n) = \Theta(n^{\log_2 7})\).

2. La condizione due è ovviamente non verificata in quanto \( f(n) \notin \Theta(n^{\log_2 7}) \).

3. In questo caso abbiamo che \( a\,f(n/b) = \frac{63}{8}\,n^2 > \frac{9}{2}\,n^2. \) La condizione è quindi non verificata.

Sarebbe stato sufficiente verificare la prima condizione in quanto le varie condizioni non si possono verificare contemporaneamente, ma ho preferito farle tutte per completezza.