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)!].