Субекспоненцијално време

У теорији сложености, субекспоненцијално време је време извршавања алгоритама које је веће од полиномијалног времена (суперполиномијално време), али мање од експоненцијланог времена. Један пример је најбољи познати, класични алгоритам за факторизацију целих бројева који захтева приближно $O(2^{{(\log N)}^{1/3}}).$ Алгоритми који захтевају субекспоненцијално време се сматрају рачунарски неизводљивим за велике вредности улаза.

Алгоритам чији улаз има дужину n је субекспоненцијални алгоритам, ако је за његово извршавање у најгорем случају потребно време величине $\exp(o(n))$.

Види још

• Експоненцијално време
• Полиномијално време
• Нотација великог O