Complexity of finding binomial coefficient which equals to a number

Question

Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).

How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$ ?

---

For example, given the input $m=8436285$, one may output $n=27, k=10$.

---

A naive algorithm for the problem would go over all possible values for $n$, and search for a value of $k$ which satisfies the property.

A simple observation is that there no need to check values of $n$ smaller than $\log m$ or larger than $O(\sqrt m)$. However (even if we could check only $O(1)$ possible $k$ values per $n$ value) this ends up in an inefficient algorithm which is exponential in the input size.

An alternative approach would be to go over the possible values of $k$ (it's enough to check $\{2,3,\ldots,2\log m\}$) and for each check for possible $n$ values. We can then use: $$\left(\frac{n}{k}\right)^k<{n\choose k}< \frac{n^k}{k!}$$

So for a given $k$ we only need to check $n$ values in the range $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$, Doing so using binary search (when $k$ is fixed, $n \choose k$ is monotonically increasing in $n$), this gives a polynomial algorithm running in $O(\log^2m)$.

This still seems inefficient to me and I guess that this could be solved in linear time (in the input size).

Answer 1

It is not true that $(n-k)^k<{n\choose k}$. For example ${9\choose 2} = 36 < 49 = (9-2)^2$.

I haven't (yet) found a subtle solution using arithmetic properties of the binomial coefficients, however I can suggest a somewhat bruteforce one if that helps :-)

You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt[k]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.

The complexity of a Newton-Raphson search only depends on the complexity of computing the function and its derivative, and the number of digits required for the solution (in our case we just need the closest integer).

So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.