Exponential time

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

${\displaystyle \text{EXP}=\underset{c\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}\text{DTIME}\left(2^{n^c}\right)}$

Sometimes, exponential time is used to refer to algorithms that have T(n) = 2O(n), where the exponent is at most a linear function of n. This gives rise to the complexity class E.

${\displaystyle \text{E}=\underset{c\in <!--\; \in \; -->\mathbb{N}}{\bigcup <!--\; \bigcup \; -->}\text{DTIME}\left(2^{cn}\right)}$