Expliquer comment nC2 est Θ (n^2)

Question

Dans le livre CLRS, en page 69, on dit que nC2 est Θ (n^2) dans l'unité diviser pour régner (U-4). Quelqu'un peut-il expalin comment ce résultat est vrai?

Answer 1

nC2 = n * (n-1)/2 = (n^2-n)/2;

Conseil:

(n^2-n)/2 sera supérieure à c1*(n^2) pour certaines constantes comme c1 < 1/4 et pour la valeur de n = 2. De même, il sera inférieur à c2*n^2 pour les valeurs c2 = 1 et n = 2. Donc, voici une situation de type sandwich. De même, il sera pris en sandwich pour les autres valeurs de n et les constantes c. Par conséquent, nC2 is Θ(n^2).