# Simplify complexity of n multichoose k

I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $$k$$ may be greater than $$n$$ and they grow independently.

Specifically, I'd expect some explicit exponential expression. The best I could find so far is that based on Stirling's approximation $$O(n!) \approx O((n/2)^n)$$, so I can use that, but I wondered if I could get anything nicer.

$$O\left({{n+k-1}\choose{k}}\right) = O(?)$$

• This is not exactly very helpful but very interesting Ramanujan’s factorial approximation Jan 2, 2013 at 10:45
• Thanks, $n! \sim \sqrt{\pi} \left(\frac{n}{e}\right)^n \sqrt{8n^3 + 4n^2 + n + \frac{1}{30}}$ looks like a cool approximation, but indeed it doesn't seem to help simplify this. Jan 2, 2013 at 11:02

Edit: This answer is for $k<n$. Without bounding $k$ in terms of $n$ the expression is unbounded.

If $k=n-1$ then your expression becomes $O\left ({{2(n-1)}\choose{n-1}}\right)$. Notice that by Stirling's formula for any $0<\alpha<1$ $${m \choose {\alpha m}}= \Theta(m^{-{1/2}} 2^{H(\alpha)m}),$$ where $H(q)=-q \log q - (1-q) \log (1-q)$ is the binary entropy. In particular $H(1/2)=1$. Therefore we have for $k=n-1$ $$O\left ({{2(n-1)}\choose{n-1}}\right)=\Theta((2n-2)^{-{1/2}} 2^{2n-2})=\Theta\left(\frac{ 4^{n}}{\sqrt{n}}\right).$$

Since the upper bound $k=n-1$ is the worst case ( I leave it as an exercise to show this), your expression is $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$.

• Thanks, exactly what I was looking for! and it's yet another thing motivating me to study information theory. Jan 2, 2013 at 11:47
• @Falcor84: I had a smaller typo in the last transition. The square root part hast to go to the denominator. Hence the bound is slightly better than the one presented by Paresh. (Actually, the bound is asymptotically tight.) Jan 2, 2013 at 15:39
• I too should have noticed that little minus sign, thanks again. Jan 2, 2013 at 16:06
• Your "left as an exercise" statement that $k = n-1$ is the worst case is wrong. If $n=3$, the expression is ${k+2 \choose k} = {k+2 \choose 2} = \frac{(k+1)(k+2)}{2}$. This is not always less than ${4 \choose 2} = 6$. Jan 5, 2013 at 13:11
• Since ${{n+k-1}\choose{k}} = {{n+k-1}\choose{n-1}}$, the problem is symmetrical in $n$ and $k$ (which can grow without relation in my case). Therefore, I suppose, the more accurate answer would be to replace n in the final part of the answer with $x := max(n,k)$ Jan 5, 2013 at 23:30

Wolfram says Sondow (2005) and Sondow and Zudilin (2006) noted the inequality: $$\frac{1}{4rm}\left[\frac{(r+1)^{r+1}}{r^r}\right]^m < {(r+1)m \choose m} < \left[\frac{(r+1)^{r+1}}{r^r}\right]^m$$ for $m$ a positive integer and $r\ge 1$ a real number.

We can then use $${n+k-1\choose k} < {n+k\choose k} = {(r + 1)m \choose m}$$ with $r = \frac{n}{k}$ and $m = k$.

Then we have $${n+k-1\choose k} < \left[\frac{(r+1)^{r+1}}{r^r}\right]^m = \left(\frac{n+k}{k}\right)^{n+k}$$

Now, the binomial expression has the highest value at the middle of the Pascal's triangle. So, in our case, $n+k = 2k$ or at $k = n$.

Substituting that in the above inequality, we get: $${n+k-1\choose k} < 2^{2n} = 4^n$$.

Therefore, a tighter bound is $${n+k-1\choose k} = O(4^n)$$.

You can also see that the lower bound for the maximum value is $${n+k-1\choose k} = \Omega\left(\frac{4^n}{n}\right)$$

References:
 Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
 Sondow, J. and Zudilin, W. "Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper" Ramanujan J. 12, 225-244, 2006.