# What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$

What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$?

$$\frac{1}{2^n} {{n}\choose{(n+2)/2}} = \frac{1}{2^n} \frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$$

The numerator and denominator in $\frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$ will take $O(n)$ multiplications.

$2^n$ will take $n$ multiplications.

So in total, there will be $O(n)$ multiplications. Is it the correct time complexity?

• The number of multiplications is indeed $O(n)$ if that's what you mean by time complexity. Note that you can compute $2^n$ in $\log(n)$ multiplications by binary exponentiation. But what about the cost of the multiplications themselves?
– PKG
Oct 24 '12 at 20:34
• I don't know. 
– Tim
Oct 24 '12 at 20:50
• Maybe there is a way to compute the binomial that takes less multiplications? (And yes, you have to state what you want to count resp. what constitutes constant effort).
– Raphael
Oct 25 '12 at 11:01
• @Raphael: What can constitutes constant effort, usually in analysis of algorithms?
– Tim
Oct 25 '12 at 11:17
• Depends. Considering multiplications and divisions constant effort, but not exponentiation, is quite common, but not helpful in all contexts. I guess you want to count all arithmetic operations.
– Raphael
Oct 25 '12 at 11:19