¿Qué es la complejidad del tiempo polinomial? Si la complejidad temporal de un algoritmo es O[(√n)!], ¿es complejidad temporal polinómica?

La complejidad del tiempo polinomial significa que hay un número positivo p (independiente de n) tal que la complejidad del tiempo es O(n^p)

La tasa de crecimiento de (√n) ! Más rápido que cualquier polinomio, si la notación O grande se reemplaza por la notación Theta grande, entonces Theta[(√n)!] no debe ser una complejidad temporal polinomial, porque según la fórmula de Stirling, Theta[(√n)]= Theta(√n^ {√n+1/2}/e^{√n}), cuando n es lo suficientemente grande, es mayor que cualquier n^p.

Pero cabe señalar que Con solo mirar O [(√n)!] no se puede determinar si se trata de una complejidad de tiempo polinomial, porque la notación O grande es solo un límite superior, incluso O (1) se puede escribir como O [(√n)!].