Is 2 n an exponential function?

More precise definition of exponential

The definition of polynomial is pretty much universal and straightforward so I won't discuss it further.

The definition of Big O is also quite universal, you just have to think carefully about the M and the x0 in the Wikipedia definition and work through some examples.

So in this answer I would like to focus on the precise definition of the exponential as it requires a bit more thought/is less well known/is less universal, especially when you start to think about some edge cases. I will then contrast it with polynomials a bit further below

• https://cstheory.stackexchange.com/questions/22588/is-it-right-to-call-2-sqrtn-exponential
• https://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial

The most common definition of exponential time is:

2^{polymonial(n)}

where polynomial is a polynomial that:

• is not constant, e.g. 1, otherwise the time is also constant
• the highest order term has a positive coefficient, otherwise it goes to zero at infinity, e.g. 2^{-n^2 + 2n + 1}

so a polynomial such as this would be good:

2^{n^2 + 2n + 1}

Note that the base 2 could be any number > 1 and the definition would still be valid because we can transform the base by multiplying the exponent, e.g.:

8^{polymonial(n)} = (2^3)^{polymonial(n)} = 2^{3 * polymonial(n)}

and 3 * polymonial(n) is also a polynomial.

Also note that constant addition does not matter, e.g. 2^{n + 1} = 2 * 2^{n} and so the + 1 does not matter for big O notation.

Therefore, two possible nice big O equivalent choices for a canonical "smallest exponential" would be for any small positive e either of:

(1 + e)^{n}
2^{en}

for very small e.

The highest order term of the polynomial in the exponent in both cases is n^1, order one, and therefore the smallest possible non-constant polynomial.

Those two choices are equivalent, because as saw earlier, we can transform base changes into an exponent multiplier.

Superpolynomial and sub-exponential

But note that the above definition excludes some still very big things that show up in practice and that we would be tempted to call "exponential", e.g.:

• 2^{n^{1/2}}. This is a bit like a polynomial, but it is not a polynomial because polynomial powers must be integers, and here we have 1/2
• 2^{log_2(n)^2}

Those functions are still very large, because they grow faster than any polynomial.

But strictly speaking, they are big O smaller than the exponentials in our strict definition of exponential!

This motivates the following definitions:

• superpolynomial: grows faster than any polynomial
• subexponential: grows less fast than any exponential, i.e. (1 + e)^{n}

and all the examples given above in this section fall into both of those categories. TODO proof.

Keep in mind that if you put something very small on the exponential, it might go back to polynomial of course, e.g.:

2^{log_2(n)} = n

And that is also true for anything smaller than log_2, e.g.:

2^{log_2(log_2(n))} = log_2(n)

is sub-polynomial.

Important superpolynomial and sub-exponential examples

• the general number field sieve the fastest 2020-known algorithm for integer factorization, see also: What is the fastest integer factorization algorithm? That algorithm has complexity of the form:

  e^{(k + o(1))(ln(n)^(1/3) * ln(ln(n)))^(2/3)}
  

  where n is the factored number, and the little-o notation o(1) means a term that goes to 0 at infinity.

  That complexity even has a named generalization as it presumably occurs in other analyses: L-notation.

  Note that the above expression itself is clearly polynomial in n, because it is smaller than e^{ln(n)^(1/3) * ln(n))^(2/3)} = e^{ln(n)} = n.

  However, in the context of factorization, what really matters is note n, but rather "the number of digits of n", because cryptography parties can easily generate crypto keys that are twice as large. And the number of digits grows as log_2. So in that complexity, what we really care about is something like:

  e^{(k + o(1))(n^(1/3) * ln(n)^(2/3)}
  

  which is of course both superpolynomial and sub-exponential.

  The fantastic answer at: What would cause an algorithm to have O(log log n) complexity? gives an intuitive explanation of where the O(log log n) comes from: while log n comes from an algorithm that removes half of the options at each step, and log log n comes from an algorithm that reduces the options to the square root of the total at each step!

• https://quantumalgorithmzoo.org/ contains a list of algorithms which might be of interest to quantum computers, and in most cases, the quantum speedup relative to a classical computer is not strictly exponential, but rather superpolynomial. However, as this answer will have hopefully highlighted, this is still extremely significant and revolutionary. Understanding that repository is what originally motivated this answer :-)

  It is also worth noting that we currently do not expect quantum computers to solve NP-complete problems, which are also generally expected to require exponential time to solve. But there is no proof otherwise either. See also: https://cs.stackexchange.com/questions/130470/can-quantum-computing-help-solve-np-complete-problems

https://math.stackexchange.com/questions/3975382/what-problems-are-known-to-be-require-superpolynomial-time-or-greater-to-solve asks about any interesting algorithms that have been proven superpolynomial (and presumably with proof of optimality, otherwise the general number sieve would be an obvious choice, but we don't 2020-know if it is optimal or not)

Proof that exponential is always larger than polynomial at infinity

https://math.stackexchange.com/questions/3975382/what-problems-are-known-to-be-require-superpolynomial-time-or-greater-to-solve

Discussions of different possible definitions of sub-exponential

• https://cstheory.stackexchange.com/questions/22588/is-it-right-to-call-2-sqrtn-exponential
• https://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial
• https://en.wikipedia.org/w/index.php?title=Time_complexity&oldid=1026049783#Sub-exponential_time

How do you know if a function is exponential or not?

Is n 2 polynomial or exponential?

Is 2 sqrt n exponential?

What makes an exponential function?