# How to show that the complexity of a function is $O(\text{polynomial})$

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.

-
In other words $f(n)=\binom{n}{\log n}$. – Henning Makholm Dec 28 '11 at 16:25
yes, I just don't know how to type that... – Belgi Dec 28 '11 at 16:26

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))$.
"if $\log n > x$ then $\binom{n}{x}<\binom{n}{\log n}$" can you explain why ? if you replace log(n) to any y s.t y>x it's not true but it seem to work with log(n)...+1 for a very good answer – Belgi Dec 28 '11 at 21:25
I should have used $\leq$ instead of $<$, which I will fix. The reason this works is $\binom{n}{x}$ increases as $x$ increases whenever $x<n/2$, so since $x<\log n<n/2$ we have $\binom{n}{x}\leq\binom{n}{\log n}$. – Alex Becker Dec 28 '11 at 22:13
@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. – Srivatsan Dec 31 '11 at 4:21