Probar n! es completamente constructible en el tiempo

Acabamos de terminar nuestra clase de "Construcibilidad de tiempo" en clase la semana pasada y, por el bien de nosotros, mostramos que $n^k, 2^n$ son completamente construibles en el tiempo, es decir, existe una máquina de Turing (determinista de múltiples cintas) que para $n$ dado, se detiene después de exactamente $f(n)$ pasos, y solo pregunté si ahora podíamos demostrar que $n!$ es completamente construible en el tiempo (y siguió adelante).

No estoy seguro de cómo va la prueba, pero creo que tiene que usar $n^k$ la capacidad de construcción del tiempo hasta cierto punto, o alguna identidad que involucra factoriales, ya que mostramos $n^k$ es (totalmente) construible en el tiempo usando $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Las sugerencias también serían apreciadas, de verdad. Gracias por adelantado.

Supongamos que tenemos encontrar $n!$ en entrada $n$. Nuestra complejidad son los términos de longitud de la entrada (asumimos que es$L=O(logn)$) Multiplicación de un$k$ poco a poco $l$ número de bit a través de tomas de multiplicación estándar $O(kl)$ operaciones (también después de la multiplicación del número de bits en el resultado si $O(k+l)$) Multiplicamos linealmente en un ciclo de$1$ a $n$ Llegar $n!$. Por lo tanto, el número de operaciones realizadas está limitado por$\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Por lo tanto, es espacio y tiempo construible.