解釋nC2是如何在Θ（n^2）

Question

在書CLRS，在第69頁，它說，在單位分而治之（U - 4）nC2是Θ（n^2）。任何人都可以expalin如何這個結果是真實的？

Answer 1

nC2 = n *（n-1）/ 2 =（n^2-n）/ 2;

提示：

(n^2-n)/2會比c1*(n^2)像c1 < 1/4一些常量和爲n = 2值。類似地，對於值c2 = 1和n = 2，其將小於c2*n^2。所以，這是一個像情況一樣的三明治。同樣，它將夾在n和常量c的其他值之間。因此，nC2 is Θ(n^2)。