Esercizio - ricorrenza con parti intere, Master Theorem e induzione parametrica (simulazione d'esame 2025-26, es. 1)

Teoria usata: Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni →, Induzione parametrica - limitazioni esatte delle ricorrenzeL'induzione parametrica prova una limitazione T(n) <= cn+d (o >=) con costanti c e d incognite: si simula la verifica per induzione, si raccolgono i vincoli su c e d dalla base e dal passo HP => TH, e se l'intersezione non è vuota si sceglie la coppia migliore. Per MAX dà esattamente T(n) = n-1; può fallire anche con guess veri (si aggiunge un parametro o un termine di ordine inferiore).Induzione parametrica - limitazioni esatte delle ricorrenze →, Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →.

La ricorrenza ha due sottoistanze di taglia diversa ($\lfloor n/4\rfloor$ e $\lfloor n/6\rfloor$) e arrotondamenti interi: il Master Theorem non si applica direttamente. Il punto (a) la maggiora con una ricorrenza "da Master Theorem", il punto (c) la tratta direttamente con l'induzione parametrica.

(a) La ricorrenza $T'$

Poiché $\lfloor n/6\rfloor \le \lfloor n/4\rfloor$, la seconda chiamata ha argomento non più grande della prima: se $T'$ è non decrescente, si può maggiorarla con una terza chiamata su $\lfloor n/4\rfloor$. Si pone $$T'(n) = \begin{cases} 1 & n \le 6 \\ 3\,T'\!\left(\lfloor n/4 \rfloor\right) + n^2 & n > 6, \end{cases}$$ cioè $a = 3$, $b = 4$, $w(n) = n^2$ (con $n_0 = 6$ e arrotondamento per difetto: la forma di Master Theorem estesa).

$T'$ è non decrescente. Si prova $T'(n) \le T'(n+1)$ per ogni $n \ge 1$, per induzione forte. Per $n + 1 \le 6$ i valori sono uguali; per $n = 6$: $T'(6) = 1 \le T'(7) = 3T'(1) + 49 = 52$. Per $n \ge 7$: $$T'(n+1) - T'(n) = 3\bigl[T'(\lfloor (n+1)/4\rfloor) - T'(\lfloor n/4\rfloor)\bigr] + (2n + 1) \ge 0,$$ perché $\lfloor (n+1)/4\rfloor$ è uguale a $\lfloor n/4\rfloor$ oppure lo supera di $1$ (e in quel caso la differenza tra le $T'$ è $\ge 0$ per ipotesi induttiva, essendo gli argomenti minori di $n$), e $2n + 1 > 0$. (In generale: se $s$, $f$ e $w$ sono non decrescenti lo è anche la soluzione.)

$T(n) \le T'(n)$ per ogni $n \ge 1$, per induzione forte su $n$.

• [B] Per $n \le 6$: $T(n) = 1 = T'(n)$.
• [HP] $T(k) \le T'(k)$ per $1 \le k < n$, con $n > 6$.
• [TH] Per $n > 6$ gli argomenti $\lfloor n/6\rfloor$ e $\lfloor n/4\rfloor$ sono $\ge 1$ e $< n$, quindi $$\begin{aligned} T(n) &= 2T(\lfloor n/4\rfloor) + T(\lfloor n/6\rfloor) + n^2 && \text{(definizione di } T) \\ &\le 2T'(\lfloor n/4\rfloor) + T'(\lfloor n/6\rfloor) + n^2 && \text{(HP, perché } 1 \le \lfloor n/6\rfloor \le \lfloor n/4\rfloor < n) \\ &\le 3T'(\lfloor n/4\rfloor) + n^2 && (T' \text{ non decrescente e } \lfloor n/6\rfloor \le \lfloor n/4\rfloor) \\ &= T'(n) && \text{(definizione di } T'). \end{aligned}$$

(b) Il Master Theorem per $T'$

La funzione di soglia è $n^{\log_b a} = n^{\log_4 3}$, con $\log_4 3 = \frac{\ln 3}{\ln 4} \approx 0{,}79$. Il lavoro $w(n) = n^2$ è polinomiale con esponente $2 > \log_4 3$: per esempio con $\varepsilon = 1$, $$w(n) = n^2 = \Omega\bigl(n^{\log_4 3 + 1}\bigr) = \Omega\bigl(n^{1{,}79}\bigr).$$ La regolarità vale per i lavori polinomiali; esplicitamente $a\,w(n/b) = 3\left(\frac n4\right)^2 = \frac{3}{16}\,n^2 = \frac3{16}\,w(n)$, quindi $c = \frac{3}{16} < 1$. Siamo nel Caso 3: $$T'(n) = \Theta\bigl(w(n)\bigr) = \Theta(n^2).$$ Quindi $f(n) = n^2$. (Numericamente $T'(n)/n^2 \to \frac{16}{13} \approx 1{,}2308$: infatti i livelli costano $n^2\left(\frac3{16}\right)^\ell$ e $\sum_\ell \left(\frac3{16}\right)^\ell = \frac{16}{13}$.)

(c) Induzione parametrica per $T(n) \le d\,n^2$

Guess: $\exists\, d \in \mathbb{R}^+ : T(n) \le d\,n^2$ per ogni $n \ge 1$.

[B] Per $1 \le n \le 6$: $T(n) = 1 \overset{?}{\le} d\,n^2 \iff d \ge \frac1{n^2}$. Il vincolo più stringente è per $n = 1$: $$d \ge 1.$$

[HP $\Rightarrow$ TH] Si assume $T(k) \le d\,k^2$ per $1 \le k < n$, con $n > 6$; gli argomenti $\lfloor n/4\rfloor, \lfloor n/6\rfloor$ stanno in $[1, n-1]$. Usando poi $\lfloor n/4\rfloor \le n/4$ e $\lfloor n/6\rfloor \le n/6$ (e $d > 0$): $$\begin{aligned} T(n) &= 2\,T(\lfloor n/4\rfloor) + T(\lfloor n/6\rfloor) + n^2 \\ &\le 2\,d\,\lfloor n/4\rfloor^2 + d\,\lfloor n/6\rfloor^2 + n^2 \\ &\le 2\,d\,\frac{n^2}{16} + d\,\frac{n^2}{36} + n^2 \ \overset{?}{\le}\ d\,n^2. \end{aligned}$$ Dividendo per $n^2 > 0$: $\ \frac d8 + \frac d{36} + 1 \le d \iff d\left(1 - \frac18 - \frac1{36}\right) \ge 1$. Calcolo: $1 - \frac18 - \frac1{36} = \frac{72 - 9 - 2}{72} = \frac{61}{72}$. Quindi $$d \ge \frac{72}{61} \approx 1{,}1803.$$

Intersezione. I due vincoli sono $d \ge 1$ e $d \ge \frac{72}{61}$; il secondo è più stringente (non lo si può evitare con la base). Si sceglie il minimo ammissibile: $$\boxed{T(n) \le \tfrac{72}{61}\,n^2 \quad \forall n \ge 1.}$$ Se si prendesse $d = 1{,}1 < \frac{72}{61}$ il passo fallirebbe: $\frac{2\cdot1{,}1}{16} + \frac{1{,}1}{36} + 1 = 1{,}168 > 1{,}1$.

Controlli. Per $n = 7..12$ i valori esatti sono $T = 52, 67, 84, 103, 124, 147$ (per esempio $T(7) = 2T(1) + T(1) + 49 = 52$ e $T(12) = 2T(3) + T(2) + 144 = 147$), e $\frac{72}{61}n^2$ vale $57{,}8$ per $n = 7$ e $169{,}9$ per $n = 12$. Con un programma si è verificato $T(n) \le \frac{72}{61}n^2$ per $n < 50\,000$, e $T(n) \le T'(n)$ per $n < 200\,000$. La costante è quasi ottima: il massimo di $T(n)/n^2$ per $n < 200\,000$ è $1{,}180327$, contro $72/61 = 1{,}180328$: infatti per $n$ grande $T(n) \approx n^2\sum_\ell\left(\frac1{8} + \frac1{36}\right)^\ell = \frac{72}{61}n^2$.

from functools import lru_cache
from fractions import Fraction

@lru_cache(None)
def T(n):  return 1 if n <= 6 else 2*T(n//4) + T(n//6) + n*n
@lru_cache(None)
def Tp(n): return 1 if n <= 6 else 3*Tp(n//4) + n*n

assert all(T(n) <= Tp(n) for n in range(1, 200000))
assert all(Fraction(T(n)) <= Fraction(72, 61) * n * n for n in range(1, 50000))
print([T(n) for n in range(7, 13)])      # [52, 67, 84, 103, 124, 147]