2
$\begingroup$

Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$.

What is the best time and space complexity of calculating $n!$?

P.S. I do not have any idea about this topic. I was using MATLAB and I needed to compute $200!$ but it said "Out of memory"!! That's why I am asking.

$\endgroup$
  • $\begingroup$ Quick note: 200! is a huge number, and you won't be able to store it into your standard data type anyway. For example, PARI/GP can handle such computations efficiently. $\endgroup$ – Juho Mar 29 '14 at 21:33
  • $\begingroup$ Ok thanks. So the problem is the space? The algorithm used in MATALB has exponential space complexity (say)? Am I right? $\endgroup$ – x.y.z... Mar 29 '14 at 21:36
  • $\begingroup$ 375 digits should hardly break the (memory) bank. And computing factorials needs nothing like exponential space. Logarithmic space with respect to the value of the answer or polynomial (linear?) with respect to the number of digits will do just fine. $\endgroup$ – David Richerby Mar 29 '14 at 23:37
2
$\begingroup$

Stirling's formula shows that $\log m! = \Theta(m\log m)$. In terms of the length $n = |m|$, we get $|m!| = \Theta(n2^n)$, and so $m!$ cannot be bounded by a polynomial in $m$. A reasonable algorithm for calculating $m!$ exactly is using the formula $m! = m \cdot (m-1) \cdots 1$. This algorithm uses quasilinear time and linear space (in the output size). For estimating $m!$, you can use the asymptotic series extending Stirling's formula.

Since $m!$ grows very large, there is no real need to calculate $m!$, you can just store all relevant values in a table (a value is relevant if it can be stored as a machine integer, though if you use bignums then more values become relevant). You can find the values in such a table on the web.

Things become more interesting when you're after $\log m!$, since now a table would be too big. Fortunately, MATLAB can compute the $\Gamma$ function which satisfies $\Gamma(m+1) = m!$ (it is the unique log concave function with this property) and its logarithm $\ln \Gamma$ — use the functions gamma and gammaln.

$\endgroup$

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.