Cómo mostrar que la complejidad de una función es $O(\text{polynomial})$

Question

Deje $A=\{1,2,4,8,16,32,...,2^k,...\}$, y deje $f:A\to \mathbb{N}$ ser definido por : $$f(n)=\binom{n}{\log n}=\frac{n!}{(\log n)!*(n-\log n)!}$$

Me gustaría saber si existe un polinomio $P(n)$ tal que $f(n)=O(P(n))$.

Esto me puede ayudar en una pregunta que me hacen en la computabilidad, así que no es de un libro de texto o algo así, si el análisis es complicado que probablemente no es el camino.

Answer 1

Por desgracia, $f(n)\neq O(P(n))$ para cualquier polinomio $P(n)$. Para ver esto, observe que $\log n < n/2$ $n>2$ así que si $\log n > x$$\binom{n}{x}\leq\binom{n}{\log n}$$n>2$. Supongamos que tenemos $f(n)=O(P(n))$ para algunos polinomio $P(n)$ grado $d$. Pero $\binom{n}{\log n}\geq\binom{n}{d+1} = \frac{n(n-1)\cdots(n-d)}{(d+1)!}$ para suficientemente grande $n$, y esto es un polinomio de grado $d+1$$f(n)\neq O(P(n))$.