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. $$Oleft({{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 $Oleft ({{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$ $$Oleft ({{2(n-1)}choose{n-1}}right)=Theta((2n-2)^{-{1/2}} 2^{2n-2})=Thetaleft(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 $Oleft(frac{ 4^{n}}{sqrt{n}}right)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7691
