Exponential time

Exponential time

An algorithm is said to be exponential time, if ${\displaystyle T(n)}$ is upper bounded by ${\displaystyle 2^{{\text{poly}}(n)}}$, where ${\displaystyle {\text{poly}}(n)}$ is some polynomial in ${\displaystyle n}$. More formally, an algorithm is exponential time if ${\displaystyle T(n)}$ is bounded by ${\displaystyle O(2^{n^{k}})}$ for some constant ${\displaystyle k}$. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP.