10
$\begingroup$

The standard algorithm to compute the factorial function $N!$ via repeated multiplications has complexity $\mathcal{O}(N)$, in the model in which each operation costs 1, no matter how many digits the operands have. Intuitively, it would seem that this cost could not be improved.

However, how can we be sure? What if there is some clever equivalent algorithm with complexity $\mathcal{O}(\log(N))$, or $\mathcal{O}(N^{0.998})$? If so, how could we know it is possible, or find an example? If not, why not?

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ What kind of time complexity are you talking about? What is your model of computation? The length of the output is $\approx N\log N$ bits, hence under the standard computation model and standard definition of time complexity, it requires time at least $N\log N$ just to write the output, hence the function cannot be computed faster than that. $\endgroup$
    – Emil Jeřábek
    Commented Jul 2, 2023 at 8:16
  • 2
    $\begingroup$ Well, a model of computation where multiplication of exponentially large integers takes constant time is totally unrealistic. $\endgroup$
    – Emil Jeřábek
    Commented Jul 2, 2023 at 8:46
  • 6
    $\begingroup$ It seems you are interested in the algebraic circuit complexity of $N!$, as in mathworker21’s comment. There is a well known argument that, basically, $N!$ cannot have small algebraic circuits unless factoring is easy. Specifically, if $N!$ has algebraic circuits of size $s$, constructible in time (bit-complexity) $s^{O(1)}$, then integers $X$ below $N^2$ or so can be factored in time $s^{O(1)}$, using binary search to find the least $M\le N$ such that $M!\bmod X$ is not coprime to $X$, which will be a prime factor of $X$. $\endgroup$
    – Emil Jeřábek
    Commented Jul 2, 2023 at 9:06
  • 1
    $\begingroup$ @EmilJeřábek I suggest to post this as an answer. $\endgroup$
    – Federico Poloni
    Commented Jul 2, 2023 at 9:54
  • 1
    $\begingroup$ Please clarify if the supplied answer addresses the question the way you intended. $\endgroup$
    – kodlu
    Commented Jul 2, 2023 at 10:18

1 Answer 1

Reset to default
11
$\begingroup$

The thing that you are asking is the required number of integer operations for computing $N!$ starting only from $1$ and $N$, which is usually referred to as the straight-line complexity of $N!$ denoted by $\tau(N!)$. (or BSS model, though I am not sure they are indeed equivalent; they are at least highly related.)

And your main question can be rephrased in terms of the standard big-O notation as follows: $$ \tau(N!) = \Omega(N), \text{ or } \tau(N!) =O(N^{1-\epsilon}) \text{ for some constant }\epsilon? $$

The answer is the latter. Indeed, there is a known algorithm showing $\tau(N!)=O(\sqrt{N}\log^2 N)$ and if we just want to find a multiple of $N!$ then there is a subexponential algorithm $\log N$, though I never checked about the algorithms.

The most relevant references I know are as follows:

  1. "On the Ultimate Complexity of Factorials" by Qi Cheng, which shows the subexponential algorithm for computing a multiple of factorial,
  2. "ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP != P?”" by Michael Shub and Steve Smale, which emphasizes this problem.

In fact, according to the second reference, the complexity of factorial is indeed an important problem known to be connected to the algebraic version of the P=NP problem. Namely, if any multiplication of $N!$ cannot be computed in time $O({\rm poly}\log(N))$, then the algebraic version of $P\neq NP$ is true.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .