# O(2^n) runs in P… Is this true? [duplicate]

My professor doesn't always know what's actually correct or wrong - he always has to think about it for a very long time and get back to the book and read the book for a long time to answer any of our questions.

He says that

I tell you that an algorithm runs in $O(2^n)$ but yet is in $\mathsf{P}$. How can this be? Ans -> The big-$O$ notation is not a tight bound. Thus any algorithm that runs in polynomial time (e.g., $O(n^2)$) will also run in exponential time, such as $O(2^n)$. Thus, an algorithm that runs in $O(2^n)$ could be in $\mathsf{P}$.

Is he correct?

• The class P is not about algorithms but about problems decoded in languages. The correctly phrased statement would be: "I tell you that this algorithm for problem X runs in time $O(2^n)$ but yet $X$ is in P." It might therefore even be true if the algorithm runs in time $\Theta(2^n)$, the problem could be in P, if we pick an inefficient algorithm. – A.Schulz May 4 '15 at 7:59

Suppose we have an algorithm $\mathcal{A}$ that runs in $O(n^{2})$ time, this means:
There exists two constants $c$ and $n_{0}$ such that for all instances of size $n \geq n_{0}$, the time $T_{\mathcal{A}}(n)$ taken by $\mathcal{A}$ is at most $c\cdot n^{2}$. That is, $\exists c, n_{0} \forall n \geq n_{0} (T_{\mathcal{A}}(n) \leq c\cdot n^{2})$.
Note that it says $T_{\mathcal{A}}(n) \leq c\cdot n^{2}$. So for any function $f(n)$ that's 'bigger' than $n^{2}$ (i.e. $n^{2} \leq f(n)$, at least for large enough $n$), by the transitivity of $\leq$, we can also then state that $T_{\mathcal{A}}(n) \leq c\cdot f(n)$. But then we have the defintion of $T_{\mathcal{A}}(n) \in O(f(n))$.
So as $n^2 \leq 2^n$ for $n \geq 4$, and $T_{\mathcal{A}}(n) \leq c\cdot n^{2}$ we get $T_{\mathcal{A}}(n) \leq c\cdot 2^{n}$ (for all $n \geq \max\{n_{0},4\}$), and hence $T_{\mathcal{A}}(n) \in O(2^{n})$.