Induzione parametrica - limitazioni esatte delle ricorrenze

Lo srotolamento di una ricorrenza (Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →) funziona per taglie $n = b^k$ e dà una formula chiusa. Per $n$ qualunque, con parti intere $\lfloor n/2\rfloor$ e $\lceil n/2\rceil$, la forma esatta può essere difficilissima da trovare. Allora si formula un'ipotesi (un guess) sull'andamento e si cerca di dimostrarla rigorosamente: è l'induzione parametrica.

La formula chiusa trovata per $n = b^k$ suggerisce l'ordine di grandezza (non le costanti) per tutti gli $n$, se la ricorrenza è abbastanza regolare, perché fornisce un campionamento infinito dei valori. Per l'ordine di grandezza di una classe ampia di ricorrenze c'è anche un teorema pronto: 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 →.

Il metodo

Si simula la verifica per induzione su una formula chiusa le cui costanti non sono fissate ma sono parametri da determinare alla fine. Lungo la prova si accumulano vincoli sui parametri, tali che tutti i passaggi siano corretti. Per esempio, per una funzione che si ipotizza limitata da una retta, il guess è $$\exists\, c \in \mathbb{R}^+,\ d \in \mathbb{R} : \quad \forall n > 0 \quad T(n) \le c\,n + d \qquad (\text{o } T(n) \ge c\,n + d),$$ cioè $T(n) = O(n)$ (o $\Omega(n)$); se si provano entrambe le disuguaglianze si ottiene $T(n) = \Theta(n)$. La disuguaglianza è un insieme infinito di guess (uno per ogni $n$) ma $c$ e $d$ sono sempre gli stessi.

I passi, in ordine:

1. Base [B]. Si impone il guess sui valori di base di $n$: ogni $n$ di base dà un vincolo.
2. Ipotesi [HP]. Si assume il guess per tutti gli argomenti minori di $n$.
3. Passo [HP $\Rightarrow$ TH]. Si applica la definizione implicita di $T(n)$ per ottenere argomenti più piccoli; si usa [HP]; si semplifica il più possibile con uguaglianze o maggiorazioni (valide per tutti i valori dei parametri); alla fine si scrive la disequazione condizionale $\overset{?}{\le}$ il cui verificarsi, per certi valori di $c, d$, permette di concludere la tesi. Il simbolo $\overset{?}{\le}$ distingue una condizione sui parametri da una maggiorazione sempre vera.
4. Intersezione. Se l'insieme dei vincoli è non vuoto, ogni coppia ammissibile trasforma la prova in una normale induzione. Per un limite superiore conviene il $c$ più piccolo possibile (miglior costante del termine dominante); per uno inferiore il $c$ più grande.

Un'avvertenza essenziale: il procedimento non è infallibile. Se il guess è falso l'insieme dei vincoli è certamente vuoto, ma può essere vuoto anche per un guess vero, quando lo strumento non è abbastanza potente. Il fallimento non prova che il guess sia falso. Dopo aver finito, conviene confermare il risultato con una verifica per induzione standard, per individuare errori di calcolo.

Esempio 1: limite superiore per MAX

La ricorrenza di MAX, valida per ogni $n \ge 1$, è $$T(n) = \begin{cases} 0 & n = 1 \\ T\left(\lfloor n/2 \rfloor\right) + T\left(\lceil n/2 \rceil\right) + 1 & n > 1. \end{cases}$$ Guess: $\exists\, c > 0,\ d \in \mathbb{R}$ con $T(n) \le cn + d$ per ogni $n \ge 1$.

[B] $n = 1$: $T(1) = 0 \overset{?}{\le} c \cdot 1 + d$. Vincolo: $\ c + d \ge 0$.

[HP $\Rightarrow$ TH] Per $n > 1$, si applica la definizione implicita e poi [HP] ai due argomenti $\lfloor n/2\rfloor, \lceil n/2\rceil$, entrambi minori di $n$ e $\ge 1$: $$\begin{aligned} T(n) &= T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1 \\ &\le \bigl(c\lfloor n/2 \rfloor + d\bigr) + \bigl(c\lceil n/2 \rceil + d\bigr) + 1 \\ &= c\,n + (2d + 1), \end{aligned}$$ perché $\lfloor n/2 \rfloor + \lceil n/2 \rceil = n$. Per ottenere la tesi $T(n) \le cn + d$ basta che $$c\,n + (2d + 1) \overset{?}{\le} c\,n + d \iff d \le -1.$$ Vincolo: $\ d \le -1$.

Intersezione dei vincoli. Il sistema $c + d \ge 0$, $d \le -1$ ha infinite soluzioni nel piano $(c, d)$; sono i punti nella regione colorata:

Dei punti ammissibili conviene il $c$ minimo, perché è il coefficiente del termine dominante: dal vincolo $d \ge -c$ e $d \le -1$ segue $c \ge 1$, il minimo è $c = 1$ e per $c = 1$ la scelta è obbligata, $d = -1$. Si ottiene $$T(n) \le n - 1.$$

Esempio 2: limite inferiore per MAX

Si cerca $T(n) \ge c'n + d'$ per opportuni $c', d'$.

• [B] $T(1) = 0 \ge c' + d'$. Vincolo: $c' + d' \le 0$.
• [HP $\Rightarrow$ TH] $T(n) \ge (c'\lfloor n/2 \rfloor + d') + (c'\lceil n/2 \rceil + d') + 1 = c'n + (2d' + 1)$, e basta $2d' + 1 \overset{?}{\ge} d'$, cioè $d' \ge -1$.
• Per un limite inferiore si vuole $c'$ massimo: da $c' \le -d'$ e $d' \ge -1$ segue $c' \le 1$, quindi $c' = 1$ e $d' = -1$.

Quindi $T(n) \ge n - 1$, che con l'Esempio 1 dà $T(n) = n - 1$ per ogni $n$. Attenzione: è un caso fortunato. Di solito i limiti inferiore e superiore non coincidono nelle costanti e la forma analitica esatta non si trova.

Esempio 3: quando il guess più semplice fallisce

Per MAX si provi il guess più semplice $T(n) \le c\,n$, vero con $c = 1$ (perché $T(n) = n - 1 \le n$).

• [B] $0 \le c$: vincolo $c \ge 0$.
• [HP $\Rightarrow$ TH] $T(n) \le c\lfloor n/2 \rfloor + c\lceil n/2 \rceil + 1 = cn + 1$, e la condizione $cn + 1 \overset{?}{\le} cn$ non è soddisfatta da nessun $c$.

L'intersezione è vuota, anche se il guess è vero per infiniti valori di $c$: con un solo parametro lo strumento non basta, il termine $+1$ del passo non si assorbe. L'aggiunta del termine di ordine inferiore $d$ (con $d \le -1$) lo risolve. Regola pratica: si prova prima il guess con un solo parametro, e si passa a più parametri (processo più complicato) solo dopo un fallimento.

Esempio 4: un guess con $n \log n$

$$T(n) = \begin{cases} 1 & n = 1 \\ 2\,T\left(\lfloor n/2 \rfloor\right) + n & n > 1 \end{cases}$$ (il lavoro $n$ per il Conquer è come nel merge sort). Dal Master Theorem ci si aspetta $\Theta(n \log n)$. Il guess $T(n) \le c\,n\log_2 n$ cade già alla base: per $n = 1$ vale $c \cdot 1 \cdot 0 = 0 < 1 = T(1)$, qualunque sia $c$. Serve un termine lineare: si prova $$T(n) \le c\,n\log_2 n + d\,n.$$

• [B] $T(1) = 1 \le c \cdot 0 + d$. Vincolo: $d \ge 1$.
• [HP $\Rightarrow$ TH] Per $n > 1$ si ha $1 \le \lfloor n/2 \rfloor < n$, quindi [HP] vale per $\lfloor n/2\rfloor$: $$T(n) \le 2\left[c\left\lfloor \tfrac n2 \right\rfloor \log_2 \left\lfloor \tfrac n2 \right\rfloor + d\left\lfloor \tfrac n2 \right\rfloor\right] + n.$$ Ora $x \mapsto x\log_2 x$ è non decrescente per $x \ge 1$ e $\lfloor n/2\rfloor \le n/2$, quindi $\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor \le \frac n2\log_2\frac n2$; inoltre $2\lfloor n/2 \rfloor \le n$ e $d > 0$. Allora $$T(n) \le c\,n(\log_2 n - 1) + d\,n + n = c\,n\log_2 n + d\,n + (1 - c)\,n \overset{?}{\le} c\,n\log_2 n + d\,n \iff c \ge 1.$$ Vincoli: $c \ge 1$, $d \ge 1$. Il limite superiore con $c$ minimo è $c = 1$, $d = 1$: $$T(n) \le n\log_2 n + n,$$ che per $n = 2^k$ vale con l'uguaglianza (srotolando: $T(2^k) = 2^k k + 2^k$).

import math
from functools import lru_cache

@lru_cache(None)
def T(n):
    return 1 if n == 1 else 2 * T(n // 2) + n

assert all(T(n) <= n * math.log2(n) + n + 1e-9 for n in range(1, 20001))
assert all(T(2**k) == 2**k * k + 2**k for k in range(20))

Errori comuni

• Far dipendere $c$ o $d$ da $n$: le costanti sono fisse e il guess vale per tutti gli $n$.
• Usare [HP] per argomenti non minori di $n$, o dimenticare che gli argomenti delle chiamate (per esempio $\lceil n/4\rceil - 1$) devono restare $\ge 1$ per poter applicare [HP].
• Perdere vincoli della base: se la base contiene più valori di $n$, ciascuno dà un vincolo e vale il più stringente.
• Concludere "il guess è falso" perché l'intersezione è vuota: può solo essere troppo debole (manca il termine di ordine inferiore).
• Scegliere $c$ al passo [TH] senza minimizzarlo: per un limite superiore il migliore è il $c$ minimo ammissibile.

Domande d'esame

1. Si provi con l'induzione parametrica una limitazione superiore $T(n) \le cn + d$ per $T(n) = T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + 1$, $T(1) = 0$. Traccia: base $c + d \ge 0$; passo $cn + 2d + 1 \le cn + d \iff d \le -1$; scelta $c = 1$, $d = -1$.
2. Perché con il guess $T(n) \le cn$ l'induzione parametrica fallisce, e questo prova che $T(n) \le cn$ è falso? Traccia: dal passo si ottiene $cn + 1 \le cn$, impossibile; ma il guess è vero con $c = 1$ (perché $T(n) = n - 1$): lo strumento è solo troppo debole.
3. Esercizi completi con parti intere: Esercizio - ricorrenza con parti intere, Master Theorem e induzione parametrica (simulazione d'esame 2025-26, es. 1) e Esercizio - induzione parametrica con parti intere e limite lineare (compito del 9 luglio 2025, es. 1).