Prove n! é totalmente construtível no tempo

Acabamos de terminar nossa lição "Construtibilidade do tempo" na aula na semana passada e, por exemplo, mostramos que $n^k, 2^n$ são totalmente construtíveis no tempo, ou seja, existe uma máquina de Turing (determinística para várias fitas) que, para $n$ dado, pára após exatamente $f(n)$ etapas, e apenas perguntei se poderíamos provar agora $n!$ é totalmente construtível por tempo (e seguiu em frente).

Não sei ao certo como é a prova, mas acho que ela deve usar $n^k$ construtividade temporal, em certa medida, ou alguma identidade envolvendo fatoriais, pois mostramos $n^k$ é (totalmente) tempo construtível usando $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Dicas também seriam apreciadas, realmente. Desde já, obrigado.

Vamos supor que encontramos $n!$ na entrada $n$. Nossa complexidade é em termos de comprimento da entrada (assumimos que seja$L=O(logn)$) Multiplicação de um$k$ pouco a pouco $l$ número de bits via multiplicação padrão leva $O(kl)$ operações (também após o número de multiplicação de bits no resultante se $O(k+l)$) Multiplicamos linearmente em um loop de$1$ para $n$ para obter $n!$. Portanto, o número de operações realizadas é delimitado por$\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Assim, é espaço e tempo construtíveis.