Search code examples
algorithmdivide-and-conquerclrs

Explain how nC2 is Θ(n^2)

In the book CLRS, in page 69 it's said nC2 is Θ(n^2) in the unit divide and conquer(U - 4). Can anyone expalin how this result is true?

Solution

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

    Hint :

    (n^2-n)/2 will be greater than c1*(n^2) for some constants like c1 < 1/4 and for value of n = 2. Similarly it will be smaller than c2*n^2 for values of c2 = 1 and n = 2. So, here is it's a sandwich like situation. Similarly, it'll be sandwiched for other values of n and constants c. Hence, nC2 is Θ(n^2).