[Algoritmi] SEmplificazione con coefficiente binomiale

[oleg.fresi]

Nel libro da cui sto studiando algoritmi, il Cormen, nella descrizione di un algoritmo che prova a fare diverse combinazioni, precisamente $((n), (2))$. Il testo dice che $((n), (2)) = Theta(n^2)$.
Potreste spiegarmi il perchè di questa conclusione? Il testo lo da per scontato, non so su quali basi.

[apatriarca]

Hai per definizione che
\[ { n \choose 2 } = \frac{n!}{(n-2)!\,2!} = \frac{(n-2)!\,(n-1)\,n}{(n-2)!\,2} = \frac{n\,(n - 1)}{2} = \frac{n^2 - n}{2} \]

[oleg.fresi]

Grazie mille, ora mi è tutto chiaro!

[oleg.fresi]

Poi vorrei però capire un'altra cosa. Per dire che $((n),(2)) = Theta(n^2)$ non basta dire che prevale il termine di grado massimo $n^2$, ma bisogna dimostrarlo usando la definizione. Su questo il libro non si sofferma, ma lo prendo come esercizio. Per farlo bisogna determinare tre valori positivi: $c_1, c_2, n_0$ tali che
$0<=c_1n^2<=(n(n-1))/2<=c_2n^2$. Il problema che ho è capire come trovare questi valori. Potreste aiutarmi per favore?

[apatriarca]

Questi valori, se esistono, non sono unici. Di solito si prendono quelli che sono più facili da trovare. In questo caso hai per esempio che \( n/2 \geq 0 \) per ogni \(n \geq 0\), per cui
\[ \frac{n^2 - n}{2} = \frac{n^2}{2} - \frac{n}{2} \leq \frac{n^2}{2} \quad ( \forall n \geq 0 ) \]
Nell'altra direzione puoi considerare per esempio che \( n^2/2 > n \) per ogni \(n \geq 2\) da cui
\[ \frac{n^2 - n}{2} = \frac{n^2}{2} - \frac{n}{2} \geq \frac{n^2}{2} - \frac{n^2}{4} = \frac{n^2}{4} \quad (\forall n \geq 2 ) \]
Per cui in questo caso puoi usare per esempio \(c_1 = 1/4, c_2 = 1/2, n_0 = 2\).

[oleg.fresi]

Perfetto, ora finalmente ho capito, ti ringrazio tanto!