Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
"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
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. –  Srivatsan Dec 31 '11 at 4:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.