complexity of combinatorial function

How the complexity of an algorithm involved with combinatorial operations is classified.

Let's say the input is m, n, and the complexity is determined by C(m,n). (C is the combination function of choosing m from n). The question is how the complexity should be categorized instead of just giving C(m,n).

I mean, 开发者_Go百科to give an idea of the running time of an algorithm, you can say the algorithm is of polynomial, exponential time complexity. But what to do with C(m,n) ?

I know factorials can be approximated by using Stirling's approximation, but the result is still too complex to put it in a complexity class.

If you insist on retaining both m and n, then it's going to be hard to do better than Stirling's approximation. The upper bound for m alone is C(m, m/2), which is asymptotic to 2^m/√m and thus exponential.

You can't "put it into a complexity class" because it isn't a single-variable running time.

It's "asymptotic behaviour" is undefined, because which variable should we consider to approach infinite? Even if we said both approach infinite lim {n->inf, m->inf} nCm is undefined because their relative values are undefined. I.e. the behaviour depends not just on n and m being greater than a certain value, but their relative values as well.

The complexity depends on two variables, and nCm is a perfectly valid complexity function.

If you have a reasonable approximation for m relative to n then you can class it more easily. Maybe it's worthwhile working out cases, where m = O(n), m = O(1).
Or where m = [kn] and 0 <= k <= 1 is constant + Stilring's formula, gives you a nice relation in one variable while still being able to consider values of m relative to k.