CODEWITHSUNDEEP
algorithmbig-o
NmdMystery
NmdMystery

Reputation: 2878

What is the asymptotic running time of a combination?

I have the recurrence relation T(n, k) = T(n - 1, k - 1) + T(n - 2, k - 1) + ... + T(k + 1, k - 1). This is the summation of T(n - i, k - 1) from i = 1 to i = n - k + 1. Calculating the result of this by hand, I noticed that this forms pascal's triangle - T(n, k) is then (n - 1) choose (k - 1).

How would I express this as an asymptotic running time in big O notation? I can prove that T(n, k) is O(n!), but that doesn't really show the whole picture - what if n is large, but k is just as large? If n = k, then then running time is just 1.

Upvotes: 0

Views: 793

Answers (1)

IVlad
IVlad

Reputation: 43477

If you look at Pascal's triangle as a matrix, and you want to find the complexity of building that matrix up to size n x k, then the big-oh of that will be O(n*k). Obviously you can't get better than that, because that's the size of the matrix.

How do we get that? Use the following simplified recurrence for combinations:

C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

Computing just a single combination has the same complexity (if using memoization).

Upvotes: 1

Related Questions