Simplify complexity of n multichoose k

Problem Detail: 

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

Asked By : yoniLavi

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7691