5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$ – integrator Oct 28 '20 at 15:41
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Rafael Bankosegger Oct 27 '20 at 15:15
  • $\begingroup$ Yes. Your solution is also right. $\endgroup$ – Steven Oct 27 '20 at 15:20
  • $\begingroup$ Great! Thanks a lot :) $\endgroup$ – Rafael Bankosegger Oct 27 '20 at 15:25
3
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.