4
$\begingroup$

Let $A=\{1,2,4,8,16,32,...,2^k,...\}$, and let $f:A\to \mathbb{N}$ be defined by : $f(n)=\binom{n}{\log n}=\frac{n!}{(\log n)!*(n-\log n)!}$

I would like to find out if there exist a polynomial $P(n)$ such that $f(n)=O(P(n))$.

This can help me in a question I do in computability, so it's not from a text book or something so if the analysis is to complicated it's probably not the way.

  • 0
    yes, $I$ just don't know how to type that...2011-12-28

1 Answers 1

4

Unfortunately, $f(n)\neq O(P(n))$ for any polynomial $P(n)$. To see this, note that $\log n < n/2$ for $n>2$ so if $\log n > x$ then $\binom{n}{x}\leq\binom{n}{\log n}$ for $n>2$. Suppose we have $f(n)=O(P(n))$ for some polynomial $P(n)$ of degree $d$. But $\binom{n}{\log n}\geq\binom{n}{d+1} = \frac{n(n-1)\cdots(n-d)}{(d+1)!}$ for sufficiently large $n$, and this is a polynomial of degree $d+1$ so $f(n)\neq O(P(n))$.

  • 1
    @Belgi, In fact, we have the quantitative estimate $\binom{n}{\log n} \geqslant \left( \frac{n}{\log n} \right)^{\log n}$ for all $n$. This shows that the function is super-polynomial.2011-12-31