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?



Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?
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](https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine), 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.


