2 added 248 characters in body; edited body

Perhaps I don't understand correctly (edit: I didn't, see below), but isn't this a trivial problem?

The complexity of multiplication is $m(n):=O(n\lg n)$ (where $\lg:=\log_2$) for two numbers of length $n$. We can naively compute factorial recursively via the good old $$N!=\begin{cases}0 N!=\begin{cases}1 & \text{if } N=0\\ N\cdot(N-1)! & \text{if }N>0.\end{cases}$$ The length of $N$ in base $2$ is approximately $\lg N$, so multiplication has an upper bound of $m(\lg N)$. Clearly this terminates in $N$ steps and hence requires $N$ multiplications, and therefore has a complexity of $O(Nm(\lg N))=O(N\lg N\lg\lg N)$. Supposing looking up the $M$th digit is $O(1)$, it is then just $O(N\lg N\lg\lg N)$. If look-up is linear in length, then it's $O(N(\lg N)^2\lg\lg N)$.

Edit: I guess I just forgot that it should be strictly polynomial in $\lg N$, which $N(\lg N)^2\lg\lg N$ of course isn't. Sorry about that. I'll refrain from deleting this though for the sake of ... completeness?

1

Perhaps I don't understand correctly, but isn't this a trivial problem?

The complexity of multiplication is $m(n):=O(n\lg n)$ (where $\lg:=\log_2$) for two numbers of length $n$. We can naively compute factorial recursively via the good old $$N!=\begin{cases}0 & \text{if } N=0\\ N\cdot(N-1)! & \text{if }N>0.\end{cases}$$ The length of $N$ in base $2$ is approximately $\lg N$, so multiplication has an upper bound of $m(\lg N)$. Clearly this terminates in $N$ steps and hence requires $N$ multiplications, and therefore has a complexity of $O(Nm(\lg N))=O(N\lg N\lg\lg N)$. Supposing looking up the $M$th digit is $O(1)$, it is then just $O(N\lg N\lg\lg N)$. If look-up is linear in length, then it's $O(N(\lg N)^2\lg\lg N)$.