2
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ 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? $\endgroup$
    – PKG
    Oct 24 '12 at 20:34
  • $\begingroup$ I don't know. $ $ $\endgroup$
    – Tim
    Oct 24 '12 at 20:50
  • $\begingroup$ 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). $\endgroup$
    – Raphael
    Oct 25 '12 at 11:01
  • $\begingroup$ @Raphael: What can constitutes constant effort, usually in analysis of algorithms? $\endgroup$
    – Tim
    Oct 25 '12 at 11:17
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Oct 25 '12 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.