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?

I cannot fully comprehend this answer. Could anyone please elaborate on his answer Please?

  • 1
    $\begingroup$ 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. $\endgroup$ – A.Schulz May 4 '15 at 7:59

His answer is indeed correct. Like with most questions about big-oh notation, the key is to go back to the definitions.

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})$.

So giving a big-oh bound for an algorithm, only gives you an upper bound, there's nothing that says it has to be tight. Of course in practice we strive to make them as tight as possible.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.