Esercizio - induzione parametrica con parti intere e limite lineare (compito del 9 luglio 2025, es. 1)

Teoria usata: 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 →.

Il guess ($T(n) \le cn$, lineare) è dato dal testo. Il lavoro è nel passo: bisogna maggiorare le parti intere in modo da ottenere una disequazione in $c$ e $n$, e risolverla per tutti gli $n$ che entrano nel passo ($n \ge 6$).

Vincolo dalla base

Per $1 \le n \le 5$: $T(n) = 12 \overset{?}{\le} c\,n \iff c \ge \frac{12}{n}$. Il più stringente è $n = 1$: $$c \ge 12.$$

Passo induttivo

Ipotesi. $T(m) \le c\,m$ per ogni $1 \le m < n$, con $n > 5$, cioè $n \ge 6$.

Gli argomenti sono ammessi. Per $n \ge 6$: $\lfloor n/3\rfloor \ge 2$ e $\lfloor n/3\rfloor < n$; $\lceil n/4\rceil - 1 \ge \lceil 6/4\rceil - 1 = 1$ e $< n$. Quindi l'ipotesi si applica a entrambi (l'argomento $\lceil n/4\rceil - 1$ non scende mai sotto $1$, dove il guess è definito). Si ricava $$\begin{aligned} T(n) &= T(\lfloor n/3\rfloor) + 2T(\lceil n/4\rceil - 1) + 2n + 1 \\ &\le c\lfloor n/3\rfloor + 2c\bigl(\lceil n/4\rceil - 1\bigr) + 2n + 1. \end{aligned}$$

Maggiorazione delle parti intere (valida per ogni valore di $c > 0$). Si ha $\lfloor n/3\rfloor \le \frac n3$ e $\lceil n/4\rceil \le \frac n4 + \frac34$, quindi $\lceil n/4\rceil - 1 \le \frac n4 - \frac14 \le \frac n4$. La versione semplice usa solo $\lceil n/4\rceil - 1 \le \frac n4$: $$T(n) \le \frac{c\,n}{3} + 2c\,\frac n4 + 2n + 1 = \frac56\,c\,n + 2n + 1.$$ Il passo riesce se $\frac56 cn + 2n + 1 \overset{?}{\le} cn$, cioè $$\frac{c\,n}{6} \overset{?}{\ge} 2n + 1.$$

Come risolvere la disequazione. Per ogni $n \ge 6$ si vuole $c \ge \frac{6(2n+1)}{n} = 12 + \frac6n$. Il lato destro decresce con $n$, quindi il caso peggiore è il più piccolo $n$ del passo, $n = 6$: $$c \ge 12 + \frac66 = 13.$$ Equivalente geometrico: il fascio di rette $y_c = \frac{c\,x}{6}$ (tutte per l'origine) deve stare sopra la retta $y = 2x + 1$ per tutti gli $x \ge 6$; basta imporlo in $x = 6$: $c\cdot\frac66 \ge 2\cdot6 + 1 = 13$. Equivalente algebrico: da $n \ge 6$ segue $1 \le \frac n6$, quindi $2n + 1 \le 2n + \frac n6$ e basta $\frac c6 \ge 2 + \frac16$, cioè $c \ge 13$.

Intersezione dei vincoli. $c \ge 12$ (base) e $c \ge 13$ (passo): si sceglie $c = \max\{12, 13\} = 13$. $$\boxed{T(n) \le 13\,n \quad \forall n > 0.}$$

Una costante migliore: $c = 12$

La soluzione del corso si ferma a $13$, che è valida. Si può fare meglio con una maggiorazione più fine, mantenendo $\lceil n/4\rceil - 1 \le \frac{n - 1}{4}$ (perché $\lceil n/4\rceil \le \frac{n+3}4$): $$T(n) \le \frac{c\,n}{3} + 2c\,\frac{n-1}{4} + 2n + 1 = \frac56\,c\,n - \frac c2 + 2n + 1 \overset{?}{\le} c\,n \iff c\left(\frac n6 + \frac12\right) \ge 2n + 1 \iff c \ge \frac{6(2n+1)}{n+3} = 12 - \frac{30}{n+3}.$$ Il lato destro è minore di $12$ per ogni $n$: quindi $c = 12$ soddisfa il passo per tutti gli $n \ge 6$, e la base chiede già $c \ge 12$. Ne segue $T(n) \le 12\,n$, e $12$ è la costante ottima, perché $T(1) = 12$ obbliga $c \ge 12$. L'esito $13$ del metodo semplice è dunque una condizione sufficiente ma non la migliore possibile: l'induzione parametrica dà una costante che dipende dalla finezza con cui si maggiorano le parti intere.

Controlli numerici. I primi valori sono $T(6) = T(2) + 2T(1) + 13 = 12 + 24 + 13 = 49$, $T(7) = 51$, $T(8) = 53$, $T(12) = 61$ (cioè $T(n) = 2n + 37$ per $6 \le n \le 15$); i rapporti $T(n)/n$ valgono $8{,}17$ per $n = 6$, $5{,}08$ per $n = 12$, $8{,}46$ per $n = 1000$, e tendono a $12$ per $n \to \infty$ (se $T(n) \approx \gamma n$: $\gamma = \frac\gamma3 + \frac\gamma2 + 2$, quindi $\gamma = 12$). Con un programma si è verificato $T(n) \le 12n$ per $n < 300\,000$ e il massimo di $T(n)/n$ è $12$ ($n = 1, \dots, 5$).

from functools import lru_cache

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

assert all(T(n) <= 12 * n for n in range(1, 300000))
assert all(-(-n // 4) - 1 >= 1 for n in range(6, 10000))     # argomento >= 1
print([T(n) for n in range(6, 13)])                          # [49, 51, 53, 55, 57, 59, 61]