I'm reading Introduction to Algorithms 3rd Edition (Cormen and Rivest) and on page 69 in the "A brute-force solution" they state that n choose 2 = Theta (n^2). I would think it would be in Theta (n!) instead. Why is n choose 2 tightly bound to n squared? Thanks!
-
2n choose 2 = n(n+1)/2 = (n^2 + n)/2... – Dennis Meng Oct 17 '13 at 0:02
-
1@DennisMeng- It's n(n-1)/2 rather than n(n+1)/2. – templatetypedef Oct 17 '13 at 0:10
-
Of course! I for some reason was thinking that n choose k was (n!)/(k!). – Jenny Shoars Oct 17 '13 at 0:27
-
You can use the wonderful Wolfram Alpha website to get a clue: wolframalpha.com/input/… – Erel Segal-Halevi Apr 25 '17 at 17:54
n choose 2 is
n(n - 1) / 2
This is
n2 / 2 - n/2
We can see that n(n-1)/2 = Θ(n2) by taking the limit of their ratios as n goes to infinity:
limn → ∞ (n2 / 2 - n / 2) / n2 = 1/2
Since this comes out to a finite, nonzero quantity, we have n(n-1)/2 = Θ(n2).
More generally: n choose k for any fixed constant k is Θ(nk), because it's equal to
n! / (k!(n - k)!) = n(n-1)(n-2)...(n-k+1) / k!
Which is a kth-degree polynomial in n with a nonzero leading coefficient.
Hope this helps!
-
Of course! I for some reason was thinking that n choose k was (n!)/(k!). – Jenny Shoars Oct 17 '13 at 0:27
-
@JennyShoars- That would definitely be confusing. Hope this cleared things up! – templatetypedef Oct 17 '13 at 0:32
-
-
1Your last claim is only true up to
k = n / 2
, at which point thek
andn - k
in the denominator of the choose function flip dominance in the cancellation and the complexity starts decreasing again, eventually reducing ton choose n == 1
. The correct generalization is that it's atheta(min(k, n-k))
order polynomial. – pjs Aug 18 '19 at 17:29 -
1@pjs Great point. I think this depends on what we think is variable and what we think is fixed. If k is a fixed constant and n is a variable, then for sufficiently large values of n we'll have n > k/2 as needed. (We could formalize this by finding proper values of c and n_0 to make this work.) – templatetypedef Aug 18 '19 at 18:19