Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Edit: In my case, $k$ may be greater than $n$ and they grow independently.

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.

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(?)$$

share|improve this question
    
This is not exactly very helpful but very interesting Ramanujan’s factorial approximation –  Pratik Deoghare Jan 2 '13 at 10:45
    
Thanks, $n! \sim \sqrt{\pi} \left(\frac{n}{e}\right)^n \sqrt[6]{8n^3 + 4n^2 + n + \frac{1}{30}}$ looks like a cool approximation, but indeed it doesn't seem to help simplify this. –  yoniLavi Jan 2 '13 at 11:02
    
To simplify this further, it would really help to know how $k$ grows as a function of $n$. If you don't know this, you might as well leave it the way it is. Both of the current answers seem to be assuming $k < n$, for which I see no justification in your question. –  Peter Shor Jan 5 '13 at 13:00
add comment

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
Thanks, exactly what I was looking for! and it's yet another thing motivating me to study information theory. –  yoniLavi Jan 2 '13 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.) –  A.Schulz Jan 2 '13 at 15:39
    
I too should have noticed that little minus sign, thanks again. –  yoniLavi Jan 2 '13 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$. –  Peter Shor Jan 5 '13 at 13:11
1  
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)$ –  yoniLavi Jan 5 '13 at 23:30
show 1 more comment

Wolfram says Sondow (2005)[1] and Sondow and Zudilin (2006)[2] 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:
[1] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
[2] Sondow, J. and Zudilin, W. "Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper" Ramanujan J. 12, 225-244, 2006.

share|improve this answer
    
Thanks for the tighter bound –  yoniLavi Jan 2 '13 at 15:15
    
Update: the first answer by A.Schulz actually gives a tighter bound, sorry for my apparent frivolity with the approved answer. –  yoniLavi Jan 2 '13 at 16:12
    
No problem at all! –  Paresh Jan 2 '13 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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