28.2 Un primo algoritmo di PD

Parte 3 · Programmazione dinamica · Capitolo 28 · Capitolo 28: Taglio delle aste (RCP) · Dispensa, volume 3 (PDF) · Slide · Esercizi: Taglio delle aste (RCP)

• Passo 1: calcolo del valore ottimo

  Per ogni \(\ell \in \{0,1,\dots,n\}\), sia \(v(\ell)\) il valore ottimo della sottoistanza dell'RCP data da:

  1. un'asta di lunghezza \(\ell\),

  2. un insieme \(\{1,2,\dots,\ell\}\) di \(\ell\) possibili lunghezze dei pezzi,

  3. per ogni lunghezza dei pezzi \(j \in \{1,2,\dots,\ell\}\), un profitto \(p_j\).

  La formula ricorsiva per calcolare \(v(\ell)\) è la seguente:

  \[\begin{equation*} \label{eq:1} v(\ell)= \left\{ \begin{array}{ll} \displaystyle \max \bigg\{ p_j + v(\ell-j) : j \in \{1,2,\dots,\ell\}\bigg\} & \textrm{se $1\le \ell \le n$,}\\[2ex] 0 & \textrm{se $\ell=0$.} \end{array} \right. \tag{28.1} \end{equation*}\]

  • Il processo di decomposizione ricorsiva della formula \(\eqref{eq:1}\) genera \(\ell\) sottoproblemi indipendenti, ciascuno corrispondente a una possibile scelta di tagliare un primo pezzo di lunghezza \(j\) da un'asta di lunghezza \(\ell\). Qui \(v(0)=0\), perché un'asta di lunghezza \(0\) non si può tagliare e ha profitto \(0\).

  • Il valore ottimo \(v(\ell)\) si ottiene provando tutte le possibili lunghezze del primo pezzo e scegliendo quella che massimizza la somma \(p_j+v(\ell-j)\) del profitto del primo pezzo e del valore ottimo del sottoproblema residuo.

  • Quindi una soluzione ottima per un'asta di lunghezza \(\ell\) si costruisce combinando il primo pezzo scelto, di lunghezza \(j\), con una soluzione ottima del sottoproblema residuo di lunghezza \(\ell-j\).

    \(\rightsquigarrow\) Sottostruttura ottima verificata!

  • Scelte diverse della lunghezza del primo pezzo, eventualmente fatte per valori diversi di \(\ell\), possono portare alla stessa lunghezza residua; quindi lo stesso valore \(v(\ell)\) può dover essere calcolato più volte durante la valutazione ricorsiva della formula \(\eqref{eq:1}\).

    \(\rightsquigarrow\) Sottoproblemi sovrapposti verificati!

  • Un primo metodo per calcolare il valore ottimo \(v(n)\) dell'istanza dell'RCP è l'approccio top-down. Il metodo parte dalla chiamata con \(\ell=n\) e valuta ricorsivamente la formula \(\eqref{eq:1}\): ogni chiamata per un'asta di lunghezza \(\ell\) genera altre chiamate per aste di lunghezza \(\ell-j\), per ogni \(j \in \{1,2,\dots,\ell\}\), fino a raggiungere il caso base \(v(0)\).

  • L'albero di ricorsione della funzione \(v\) ha un nodo per ogni chiamata ricorsiva, etichettato con la chiamata che rappresenta. La radice rappresenta la chiamata iniziale. I figli di un nodo rappresentano le chiamate ricorsive fatte da quella chiamata. Le foglie rappresentano i casi base.

    Esempio 28.3: Albero di ricorsione

    Consideriamo l'istanza dell'RCP dell'Esempio 28.1. Questo è l'albero di ricorsione dell'approccio top-down per calcolare \(v(4)\):

    

    La funzione \(v\) viene chiamata \(16\) volte, e gli stessi sottoproblemi vengono risolti più volte: \(v(2)\) viene chiamata \(2\) volte, \(v(1)\) viene chiamata \(4\) volte e \(v(0)\) viene chiamata \(8\) volte. Tutte le altre chiamate vengono fatte una sola volta.

  • Il valore \(v(\ell)\), per una generica lunghezza dell'asta \(\ell\), si può calcolare una volta noti i valori \(v(j)\) per tutte le lunghezze minori \(j<\ell\).

    Esempio 28.4: Calcolo dei valori della funzione \(v\)

    Consideriamo l'istanza dell'RCP dell'Esempio 28.1, con un'asta di lunghezza \(n = 4\); i profitti associati alle possibili lunghezze dei pezzi sono:

    \[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

    Il valore della funzione \(v\) si può calcolare partendo dal caso base \(v(0)=0\) e calcolando poi, in ordine, i valori di \(v(1)\), \(v(2)\), \(v(3)\) e \(v(4)\), come segue:

    • Poiché conosciamo il valore di \(v(0)\), possiamo calcolare \(v(1)\) come segue:

      \[ v(1)=p_1 + v(0) = 1 + 0 = 1 \]

    • Calcolato \(v(1)\), possiamo calcolare \(v(2)\) come segue:

      \[ v(2)= \max\{p_1+v(1),p_2+v(0)\} = \max\{1+1,5+0\} = 5 \]

    • Calcolati \(v(2)\) e \(v(1)\), possiamo calcolare \(v(3)\) come segue:

      \[ v(3)= \max\{p_1+v(2),p_2+v(1),p_3+v(0)\} = \max\{1+5,5+1,8+0\} = 8 \]

    • Calcolati \(v(3)\), \(v(2)\) e \(v(1)\), possiamo calcolare \(v(4)\) come segue:

      \[\begin{align*} v(4)&= \max\{p_1+v(3),p_2+v(2),p_3+v(1),p_4+v(0)\}\\ &= \max\{1+8,5+5,8+1,9+0\} = 10 \end{align*}\]

  • Possiamo evitare di risolvere ripetutamente gli stessi sottoproblemi memorizzando il valore di ogni sottoproblema appena calcolato. I valori si memorizzano in una tabella di lookup.

  • Poiché la soluzione di un sottoproblema di valore \(v(\ell)\) dipende solo dai sottoproblemi di valore \(v(j)\), con \(j<\ell\), possiamo risolvere i sottoproblemi per valori crescenti di \(\ell\), partendo dal caso base \(v(0)=0\) fino ad arrivare a \(v(n)\): questa osservazione porta in modo naturale a un metodo molto più efficiente per calcolare il valore ottimo \(v(n)\) dell'istanza dell'RCP.

  • Un secondo metodo per calcolare il valore ottimo \(v(n)\) dell'istanza dell'RCP è l'approccio bottom-up. Il metodo parte dal caso base \(v(0)=0\) e valuta la formula \(\eqref{eq:1}\) per lunghezze crescenti dell'asta \(\ell \in \{1,2,\dots,n\}\): ogni valore \(v(\ell)\) si calcola con i valori già calcolati \(v(0), v(1), \dots, v(\ell-1)\), fino a ottenere il valore \(v(n)\) dell'istanza dell'RCP.

    Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up:

    Algoritmo: DP1

    Input: Un'istanza dell'RCP data dalla lunghezza \(n\) dell'asta e da un array \(p[1..n]\) dei profitti dei pezzi

    Output: Il valore ottimo dell'istanza dell'RCP

    1Function DP1(\(n,p\))

    2\({v} := \textnormal{new array}[0..n]\)

    3\({v}[0] \leftarrow 0\)

    4for \(\ell := 1\) to \(n\) do

    5\(\mathit{m} := 0\)

    6for \(j := 1\) to \(\ell\) do

    7if \(\mathit{m} < p[j] + {v}[\ell-j]\) then

    8\(\mathit{m} \leftarrow p[j] + {v}[\ell-j]\)

    9end

    10end

    11\({v}[\ell] \leftarrow \mathit{m}\)

    12end

    13return \({v}[n]\)

    • Il vettore \({v}[0..n]\) è la tabella di lookup: memorizza i valori ottimi di tutti i sottoproblemi, con il caso base \({v}[0]=0\).

    • Il ciclo esterno, su \(\ell \in \{1,2,\dots,n\}\), calcola \({v}[\ell]\) in ordine crescente di lunghezza dell'asta.

    • Il ciclo interno, su \(j \in \{1,2,\dots,\ell\}\), valuta tutte le possibili lunghezze del primo pezzo e tiene in \(\mathit{m}\) il valore massimo di \(p[j]+{v}[\ell-j]\).

    • Alla fine del ciclo interno, \({v}[\ell] \leftarrow \mathit{m}\) memorizza il valore ottimo \({v}[\ell]\).

    • Infine, l'algoritmo restituisce il valore ottimo \({v}[n]\) dell'istanza dell'RCP.

    Esempio 28.5: Esecuzione dell'algoritmo di PD

    Consideriamo l'istanza dell'RCP dell'Esempio 28.1, con un'asta di lunghezza \(n = 4\); i profitti associati alle possibili lunghezze dei pezzi sono:

    \[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

    Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(\ell\) e \(j\), il valore corrente di \(\mathit{m}\) e la cella \({v}[\ell]\). La cella di \(\mathit{m}\) è evidenziata in rosso quando viene aggiornata; la cella di \({v}[\ell]\) è evidenziata in blu quando viene assegnata.

    \(\ell\)	\(j\)	\({v}[\ell]\)	\(\mathit{m}\)	Azione
    \(-\)	\(-\)	0	\(-\)	\({v}[0]\leftarrow 0\)
    	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
    1	1	\(-\)	1	\(p[1]{+}{v}[0]=1{+}0=1>0\): \(\mathit{m}\leftarrow 1\)
    	\(-\)	1	1	\({v}[1]\leftarrow \mathit{m}=1\)
    	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
    2	1	\(-\)	2	\(p[1]{+}{v}[1]=1{+}1=2>0\): \(\mathit{m}\leftarrow 2\)
    	2	\(-\)	5	\(p[2]{+}{v}[0]=5{+}0=5>2\): \(\mathit{m}\leftarrow 5\)
    	\(-\)	5	5	\({v}[2]\leftarrow \mathit{m}=5\)
    	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
    3	1	\(-\)	6	\(p[1]{+}{v}[2]=1{+}5=6>0\): \(\mathit{m}\leftarrow 6\)
    	2	\(-\)	6	\(p[2]{+}{v}[1]=5{+}1=6=\mathit{m}\): nessun aggiornamento
    	3	\(-\)	8	\(p[3]{+}{v}[0]=8{+}0=8>6\): \(\mathit{m}\leftarrow 8\)
    	\(-\)	8	8	\({v}[3]\leftarrow \mathit{m}=8\)
    	\(-\)	\(-\)	0	\(\mathit{m}\leftarrow 0\)
    4	1	\(-\)	9	\(p[1]{+}{v}[3]=1{+}8=9>0\): \(\mathit{m}\leftarrow 9\)
    	2	\(-\)	10	\(p[2]{+}{v}[2]=5{+}5=10>9\): \(\mathit{m}\leftarrow 10\)
    	3	\(-\)	10	\(p[3]{+}{v}[1]=8{+}1=9<10\): nessun aggiornamento
    	4	\(-\)	10	\(p[4]{+}{v}[0]=9{+}0=9<10\): nessun aggiornamento
    	\(-\)	10	10	\({v}[4]\leftarrow \mathit{m}=10\)

    Questo è il vettore \({v}\) dopo l'esecuzione dell'algoritmo di PD:

    \[ \begin{array}{c|ccccc} \hline & {\ell = 0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{v}[\ell]} & 0 & 1 & 5 & 8 & 10 \\ \hline \end{array} \]

  • Dopo l'esecuzione dell'algoritmo di PD, il vettore \({v}\) contiene il valore ottimo \({v}[\ell]\) per ogni lunghezza dell'asta.

• Passo 2: calcolo di una soluzione ottima

  • Per calcolare una soluzione ottima è necessario memorizzare alcune informazioni aggiuntive.

  • Per ogni lunghezza dell'asta \(\ell\), oltre al valore ottimo \({v}[\ell]\), memorizziamo \({s}[\ell]\), la lunghezza del primo pezzo da tagliare in una soluzione ottima per un'asta di lunghezza \(\ell\).

  • Partendo da \(\ell=n\), il valore \({s}[\ell]\) dà la lunghezza del primo pezzo da tagliare; l'asta rimanente ha lunghezza \(\ell-{s}[\ell]\), e la stessa regola si può applicare di nuovo, e così via, finché la lunghezza residua arriva a \(0\).

    Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, con la memorizzazione delle informazioni necessarie per calcolare una soluzione ottima:

    Algoritmo: DP1_InfoSol

    Input: Un'istanza dell'RCP data dalla lunghezza \(n\) dell'asta e da un array \(p[1..n]\) dei profitti dei pezzi

    Output: Il valore ottimo dell'istanza dell'RCP e il vettore di informazioni \({s}[1..n]\)

    1Function DP1_InfoSol(\(n,p\))

    2\({v} := \textnormal{new array}[0..n]\)

    3\({s} := \textnormal{new array}[1..n]\)

    4\({v}[0] \leftarrow 0\)

    5for \(\ell := 1\) to \(n\) do

    6\(\mathit{m} := 0\)

    7\(\mathit{t} := 0\)

    8for \(j := 1\) to \(\ell\) do

    9if \(\mathit{m} < p[j] + {v}[\ell-j]\) then

    10\(\mathit{m} \leftarrow p[j] + {v}[\ell-j]\)

    11\(\mathit{t} \leftarrow j\)

    12end

    13end

    14\({v}[\ell] \leftarrow \mathit{m}\)

    15\({s}[\ell] \leftarrow \mathit{t}\)

    16end

    17return \({v}[n], {s}\)

    • L'algoritmo di PD usa la variabile temporanea aggiuntiva \(\mathit{t}\) per tenere traccia della decisione presa quando \(\mathit{m}\) viene aggiornato. Se si sceglie un primo pezzo di lunghezza \(j\), \(\mathit{t}\leftarrow j\) memorizza questa decisione. Alla fine del ciclo interno, \({s}[\ell]\leftarrow \mathit{t}\) memorizza la lunghezza del primo pezzo scelto, insieme al valore ottimo \({v}[\ell]\leftarrow \mathit{m}\).

    Esempio 28.6: Calcolo delle informazioni aggiuntive

    Consideriamo l'istanza dell'RCP dell'Esempio 28.1, con un'asta di lunghezza \(n = 4\); i profitti associati alle possibili lunghezze dei pezzi sono:

    \[ \begin{array}{l|rrrrrrr} \hline & {\ell = 1} & {\ell = 2} & {\ell = 3} & {\ell = 4} \\ \hline {p_\ell} & {1} & {5} & {8} & {9} \\ \hline \end{array} \]

    Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(\ell\) e \(j\), la cella \({s}[\ell]\), il valore corrente di \(\mathit{m}\) e il valore corrente di \(\mathit{t}\). La cella di \(\mathit{m}\) è evidenziata in rosso quando viene aggiornata; la cella di \(\mathit{t}\) e la cella di \({s}[\ell]\) sono evidenziate in blu quando vengono aggiornate.

    \(\ell\)	\(j\)	\({s}[\ell]\)	\(\mathit{m}\)	\(\mathit{t}\)	Azione
    \(-\)	\(-\)	\(-\)	\(-\)	\(-\)	Stato iniziale
    	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
    1	1	\(-\)	1	1	\(1{+}0=1>0\): \(\mathit{m}\leftarrow 1\), \(\mathit{t}\leftarrow 1\)
    	\(-\)	1	1	1	\({v}[1]\leftarrow \mathit{m}=1\), \({s}[1]\leftarrow \mathit{t}=1\)
    	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
    2	1	\(-\)	2	1	\(1{+}1=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\)
    	2	\(-\)	5	2	\(5{+}0=5>2\): \(\mathit{m}\leftarrow 5\), \(\mathit{t}\leftarrow 2\)
    	\(-\)	2	5	2	\({v}[2]\leftarrow \mathit{m}=5\), \({s}[2]\leftarrow \mathit{t}=2\)
    	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
    3	1	\(-\)	6	1	\(1{+}5=6>0\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 1\)
    	2	\(-\)	6	1	\(5{+}1=6=\mathit{m}\): nessun aggiornamento
    	3	\(-\)	8	3	\(8{+}0=8>6\): \(\mathit{m}\leftarrow 8\), \(\mathit{t}\leftarrow 3\)
    	\(-\)	3	8	3	\({v}[3]\leftarrow \mathit{m}=8\), \({s}[3]\leftarrow \mathit{t}=3\)
    	\(-\)	\(-\)	0	0	\(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\)
    4	1	\(-\)	9	1	\(1{+}8=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\)
    	2	\(-\)	10	2	\(5{+}5=10>9\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 2\)
    	3	\(-\)	10	2	\(8{+}1=9<10\): nessun aggiornamento
    	4	\(-\)	10	2	\(9{+}0=9<10\): nessun aggiornamento
    	\(-\)	2	10	2	\({v}[4]\leftarrow \mathit{m}=10\), \({s}[4]\leftarrow \mathit{t}=2\)

    Questo è il vettore \({s}\) dopo l'esecuzione dell'algoritmo di PD:

    \[ \begin{array}{c|cccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

  • Calcolato il vettore \({s}\), si può calcolare una soluzione ottima dell'istanza dell'RCP applicando ripetutamente la seguente regola, partendo da \(j=n\) e da \(x_{\ell}=0\) per ogni \(\ell \in \{1,2,\dots,n\}\):

    \[ x_{{s}[j]} \leftarrow x_{{s}[j]}+1, \qquad j \leftarrow j-{s}[j], \]

    finché \(j=0\). Si ottiene così il vettore \((x_1,x_2,\dots,x_n)\), dove ogni componente \(x_{\ell}\) è il numero di pezzi di lunghezza \(\ell\) in una soluzione ottima.

  • Il seguente pseudocodice implementa il calcolo di una soluzione ottima, dato il vettore \({s}\).

    Algoritmo: DP1_SolComputation

    Input: La lunghezza \(n\) dell'asta dell'istanza dell'RCP e il vettore \({s}[1..n]\)

    Output: Una soluzione ottima dell'istanza dell'RCP

    1Function DP1_SolComputation(\(n,{s}\))

    2\(x := \textnormal{new array}[1..n]\)

    3for \(\ell := 1\) to \(n\) do

    4\(x[\ell] \leftarrow 0\)

    5end

    6\(j := n\)

    7while \(j > 0\) do

    8\(x[{s}[j]] \leftarrow x[{s}[j]]+1\)

    9\(j \leftarrow j - {s}[j]\)

    10end

    11return \(x\)

    Esempio 28.7: Calcolo di una soluzione ottima

    Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 28.1, abbiamo il seguente vettore \({s}\):

    \[ \begin{array}{l|rrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

    Possiamo calcolare una soluzione ottima per un'asta di lunghezza \(n=4\) come segue:

    Iterazione	\(j\)	\({s}[j]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(j \leftarrow j-{s}[j]\)
    \(-\)	\(-\)	\(-\)	0	0	0	0	\(j=4\)
    \(1\)	\(4\)	\(2\)	0	1	0	0	\(j=4-2=2\)
    \(2\)	\(2\)	\(2\)	0	2	0	0	\(j=2-2=0\)

    Una soluzione ottima è il vettore:

    \[ (0,2,0,0) \]

  • La stessa procedura di calcolo, basata sul vettore \(s\), si può applicare partendo da qualunque lunghezza dell'asta \(\ell\).

    Esempio 28.8: Calcolo di soluzioni ottime per le lunghezze dell'asta 3 e 2

    Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 28.1, abbiamo il seguente vettore \({s}\):

    \[ \begin{array}{l|rrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} \\ \hline {{s}[\ell]} & 1 & 2 & 3 & 2 \\ \hline \end{array} \]

    Possiamo calcolare una soluzione ottima per un'asta di lunghezza \(3\) come segue:

    Iterazione	\(j\)	\({s}[j]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(j \leftarrow j-{s}[j]\)
    \(-\)	\(-\)	\(-\)	0	0	0	0	\(j=3\)
    \(1\)	\(3\)	\(3\)	0	0	1	0	\(j=3-3=0\)

    Una soluzione ottima è il vettore:

    \[ (0,0,1,0) \]

    Possiamo calcolare una soluzione ottima per un'asta di lunghezza \(2\) come segue:

    Iterazione	\(j\)	\({s}[j]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	\(j \leftarrow j-{s}[j]\)
    \(-\)	\(-\)	\(-\)	0	0	0	0	\(j=2\)
    \(1\)	\(2\)	\(2\)	0	1	0	0	\(j=2-2=0\)

    Una soluzione ottima è il vettore:

    \[ (0,1,0,0) \]

28.2.1 Numero di passi

• Sia \(S(n)\) il numero di passi eseguiti da DP1 nel caso peggiore, dove \(n\) è la lunghezza dell'asta. Calcoliamo \(S(n)\) contando quante volte vengono eseguite le Righe 2–Riga 13.

• Nel caso peggiore, la condizione alla riga 7 è vera a ogni iterazione del ciclo interno, e quindi la riga 8 viene eseguita tante volte quanto la riga 7. Il numero di esecuzioni delle righe rilevanti è:

  • Riga 2 viene eseguita \(1\) volta.

  • Riga 3 viene eseguita \(1\) volta.

  • Riga 4 viene eseguita \(n\) volte.

  • Riga 5 viene eseguita \(n\) volte.

  • Riga 6 viene eseguita \(\displaystyle\sum_{\ell=1}^{n}\ell\) volte.

  • Riga 7 viene eseguita \(\displaystyle\sum_{\ell=1}^{n}\ell\) volte.

  • Riga 8 viene eseguita \(\displaystyle\sum_{\ell=1}^{n}\ell\) volte.

  • Riga 11 viene eseguita \(n\) volte.

  • Riga 13 viene eseguita \(1\) volta.

  Quindi il numero totale di passi nel caso peggiore è

  \[ 1+1+n+n+\sum_{\ell=1}^{n}\ell+\sum_{\ell=1}^{n}\ell+\sum_{\ell=1}^{n}\ell+n+1 = 3+3n+3\sum_{\ell=1}^{n}\ell. \]

  Usando \(\sum_{\ell=1}^{n}\ell=\dfrac{n(n+1)}{2}\), otteniamo

  \[ S(n)=3+3n+3\cdot\frac{n(n+1)}{2} = \frac{3n^2+9n+6}{2}. \]

  Quindi

  \[ S(n)=\Theta(n^2). \]

  Infatti,

  \[ \lim_{n\to\infty} \frac{\frac{3n^2+9n+6}{2}}{n^2} = \lim_{n\to\infty} \frac{1}{2}\left(3+\frac{9}{n}+\frac{6}{n^2}\right) = \frac{3}{2}\in\mathbb{R}_{>0}. \]

  L'algoritmo di PD esegue

  \[ S(n)=\Theta(n^2) \]

  passi nel caso peggiore.

---

Avanti: 28.3 Un secondo algoritmo di PD