algorithm - 解释 nC2 如何是 Θ(n^2)

Question

在 CLRS 一书中，第 69 页中说 nC2 在单位分而治之（U - 4）中是 Θ(n^2)。谁能解释这个结果是如何正确的？

Answer 1

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

暗示 ：

(n^2-n)/2将大于c1*(n^2)某些常量，例如c1 < 1/4和 的值n = 2。同样，它将小于和c2*n^2的值。所以，这是一个类似三明治的情况。类似地，它将被夹在 n 和常数 c 的其他值中。因此，。c2 = 1n = 2nC2 is Θ(n^2)