# Upper bounds for a binomial coefficient

I have an algorithm with worst-case time complexity in $$\mathcal O (\binom{k}{p-1})$$, where $$k$$ is a parameter and $$p$$ is the input size of that algorithm. I further have determined that $$p-1 \leq k$$.

I need an argument which shows that the runtime complexity is solely a function of its parameter $$k$$, i.e. that the input size $$p$$ does not matter for runtime complexity.

My own argument goes as follows:

$$\binom{k}{p-1} = \frac{k!}{(p-1)!(k-(p-1))!} \leq k!$$ Where the first equality follows from the definition of the binomial coefficient and the second inequality follows from the observation that both $$(p-1)!$$ and $$(k-(p-1))!$$ are greater than or equal to $$1$$.

Thus the algorithm runs in $$\mathcal O (k!)$$, which is a not a function of $$p$$ as required.

Is this argument correct or am I missing something? Maybe I am overcomplicating things and there is a faster / better argument?

• "I need an argument which shows that the runtime complexity is solely a function of its parameter 𝑘, i.e. that the input size 𝑝 does not matter for runtime complexity.". Actually, it isn't quite true (for instance the exact complexity could be equal to $k\choose p-1$, which depends on $p$). What you've shown is that you can upper bound (asymptotically) the runtime by a function of $k$ alone. – integrator Oct 28 '20 at 15:41

The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows:

$$\binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k$$

Where the equality $$\sum_{i=0}^{k} \binom{k}{i} = 2^k$$ follows from the fact that the summation on the left is counting the number of possible subsets of a set with $$k$$ elements, grouped by cardinality: the $$i$$-th term of the sum (for $$i=0, \dots, k$$) is the number of subsets with exactly $$i$$ elements.

Also, using Stirling's approximation and assuming that $$k$$ is even (this is just for convenience, if it's not you can consider $$k+1$$ instead to get the same asymptotic bound):

$$\binom{k}{p-1} \le \binom{k}{k/2} = O\left( \frac{ (k/e)^k \sqrt{k} }{ k (k/2e)^k } \right) = O\left(\frac{2^k}{\sqrt{k}} \right).$$

• Right, so the righthand side of the inequality is effectively the size of the power set and the lefthand part must definitely be smaller than that since it's only a subset of the powerset. Did I get that right? But my solution is right in principle? – Rafael Bankosegger Oct 27 '20 at 15:15
• Yes. Your solution is also right. – Steven Oct 27 '20 at 15:20
• Great! Thanks a lot :) – Rafael Bankosegger Oct 27 '20 at 15:25

There are well known inequalities: $$\frac{n^k}{k^k}\leqslant \binom{n}{k}\leqslant \frac{n^k}{k!}$$

• – birneee Feb 19 at 21:13