I know that the complexity of this combination $\ {n \choose n/3}$ is of $\theta(n^{n/3})$ , but I'm in need of help proving it.
Asked
Active
Viewed 1,287 times
1 Answers
1
I assume that by "complexity" you mean the value.
In
Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$
I showed that for $n \ge 2$, $$\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n \text{ where } r_k = \frac{k^k}{(k-1)^{k-1}} $$ and, if you use Stirling's formula, you get $$\binom{kn}{n} \approx \sqrt{\dfrac{k}{2\pi n(k-1)}}r_k^{n} $$
Putting $k=3$ and $n = n/3$, this becomes for $n \ge 2$,
$\dfrac{r_3^{n/3}}{n/3+1} \le \binom{n}{n/3} < r_3^{n/3}$ where $r_3 = \frac{3^3}{2^2} = \frac{27}{4} $
and $\binom{n}{n/3} \approx \sqrt{\dfrac{9}{4\pi n}}r_3^{n/3} $.
marty cohen
- 107,799
-
Do you mean $\sim$ instead of $\approx$ ? – lhf Apr 19 '16 at 16:07
-
The ratio goes to $1$. So use whichever you want. – marty cohen Apr 19 '16 at 16:18