1
$\begingroup$

So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$.

$(2n-1)*(2n-3)*...*1$ but my professor claimed it can be done much faster in algorithmic sense, but I don't really see the way to do so. Any hints? Thanks!

$\endgroup$
  • $\begingroup$ The number $(2n-1)\cdot (2n-3)\cdots 3\cdot 1$ is known as the "double factorial" of $2n-1$, and written $(2n-1)!!$. But knowing that didn't help me find an answer to your question! $\endgroup$ – David Richerby Jun 30 '16 at 17:15
  • $\begingroup$ Perhaps your professor meant the formula $(2n)!/(2^n n!)$, though I'm not sure why this is faster. $\endgroup$ – Yuval Filmus Jun 30 '16 at 20:25
  • $\begingroup$ Adding to Yuval's answer, it's also equal to $\frac{n!}{2^n}\binom{2n}{n}$, but again that's not particularly better (worse, in fact). $\endgroup$ – Rick Decker Jul 1 '16 at 0:50
  • $\begingroup$ It is better, it changes $m$ subtractions into one bitshift and there is a trick to cut number of multiplications by half. $\endgroup$ – Evil Jul 1 '16 at 4:06
1
$\begingroup$

There is one algorithmic improvement if $n$ is large and you want to express this number for example as a decimal or binary number without any rounding errors: Let's say you have $n$ equals one billion. You will do about 500 million multiplications, and if you do this in a straightforward way, you will multiply various numbers from 1 to a bit over 4 billion digits by some small number. Multiplying an $n$ digit number by a small number takes $O(n)$ steps, so your product all in all takes $O(n^2)$ steps.

It's faster if you calculate 250 million products of up to 9 digit numbers giving 250 million 18 digit numbers, then 125 million products of 18 digit numbers giving 36 digit numbers and so on, until finally you multiply two numbers of 2 billion digits each. Multiplying $k$ digit numbers can be done in $O (k \log k)$ instead of $O (k^2)$, and therefore the total work is $O (n \log^2 n)$.

A completely different improvement for large $n$ is to use the Stirling approximation $n! \approx n^n \mathrm{e}^{-n} (2\pi n)^{1/2}$, and substitute that in the formula in Yuval's comment. Obviously that gives an approximation only.

$\endgroup$
  • $\begingroup$ This gets a bit confusing because you use $n$ to mean different things even within the same paragraph. ("$n$ is large" seems to refer to the number whose double factorial we wish to compute but they you say "$n$ digit number") $\endgroup$ – David Richerby Jul 1 '16 at 15:12

Your Answer

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

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