Upper bounds for a binomial coefficient

Question

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?

Answer 1

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). $$

Answer 2

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