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.

  • 1
    In other words $f(n)=\binom{n}{\log n}$.2011-12-28
  • 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))$.

  • 0
    "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 answer2011-12-28
  • 0
    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$\binom{n}{x}\leq\binom{n}{\log n}$. – 2011-12-28
  • 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