1

Is the Big-O of $e^n$ greater than the Big-O of $2^n$? I understand:

  • We have a single time complexity class of exponential for $2^n$, $e^n$ and $4^n$ (if I am not wrong.)
  • There is no real algorithm with $e^n$ complexity (if I am not wrong), so I am asking in the mathematical context and in the definition of Big-O.
  • Simple graphing in Desmos it shows Euler's no. to the n grows faster than $2^n$, but does that mean the Big-O of $e^n$ is also greater than Big-O of $2^n$? Am I even asking the question in a right way? Or I am mixing two different theories of Computational complexity of mathematical operations and Computational Complexity of a function in computer science? What is the right way of asking this question even?
Rócherz
  • 3,976
Mojtaba Mohammadi
  • 45

1 Answers1

2

Yes, $e^n$ is not in $O(2^n)$, and you can invent an algorithm that runs in $O(e^n)$, but not in $O(2^n)$ time (something like "sleep $\lceil e^n \rceil$ steps and then output $0$"). Time hierarchy theorem gives an example of problem that can be solved in $O(e^n)$ time, but not in $O(2^n)$ time: given a code of Turing machine, and number $n$ in unary representation, check if this Turing machine stops in $2.1^n$ steps.

However, when we speak about complexity classes, we are not always restricting ourselves to times that differ only by constant factor. In some parts of complexity theory (actually in most of it, I think), we consider classes like P (polynomial time - $O(n^k)$ for arbitrary constant $k$) and EXPTIME (exponential time - $O(2^{p(n)})$ for arbitrary polynomial $p(n)$), because we can still say a lot of interesting things in such abstraction, and determining specific degree of polynomial is less interesting, and also heavily depends on model of computation - for example, problem "is input string palindrome" is solvable in $O(n)$ time on two-tape Turing machine, but isn't solvable in $o(n^2)$ on one-tape.

mihaild
  • 15,368