請問什麽是多項式時間復雜度？若壹個算法的時間復雜度為O[(√n)!]，那麽它是不是多項式時間復雜度

(√n)!的增長速度要快於任何多項式, 如果把大O記號換成大Theta記號, 那麽Theta[(√n)!]壹定不是多項式時間復雜度, 因為由Stirling公式, Theta[(√n)]=Theta(√n^{√n+1/2}/e^{√n}), 當n充分大時大於任何n^p.

但是需要註意, 僅看O[(√n)!]不能判定是否是多項式時間復雜度, 因為大O記號只是壹個上界, 即使是O(1)也可以寫成O[(√n)!].