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