In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because $n=\log C$ we can write that $O((\log C)^22^n)=O(2^n)$ because $2^n$ grows more rapidly than $\log C$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
You are correct that the running time is $O(n^2 2^n)$, but according to the definition of big O, it is not the case that $n^2 2^n = O(2^n)$, since $n^2 2^n$ grows faster than $2^n$. What is true is that for every $\epsilon > 0$, $n^2 2^n = O((2+\epsilon)^n)$.
Often it is convenient to hide such "small" factors, and write $O(n^2 2^n) = \tilde{O}(2^n)$. The usual definition of $\tilde{O}(\cdot)$ is this: $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log g(n))^k)$. In practice this is almost always used when $g(n)$ is either a polynomial or an exponential. When $g(n)$ is a polynomial, $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log n)^k)$, and we say that $\tilde{O}$ hides polylogarithmic factors. When $g(n)$ is exponential (that is, $g(n) = e^{An^B}$ for some $A,B>0$), $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n) n^k)$, and we say that $\tilde{O}$ hides polynomial factors.
answered Nov 17, 2014 at 23:21
-
1$\begingroup$ Ahhh, $\tilde{O}$ -- the art of (or excuse for?) being even more sloppy!</snark> $\endgroup$– Raphael ♦Nov 17, 2014 at 23:30
-
$\begingroup$ thank you very much. So, still can we say that the algorithm runs in exponential time? Implying that $O((2+e)^n) = O(2^n)$ for some small enough $e$? $\endgroup$ Nov 18, 2014 at 7:09
-
$\begingroup$ No, $O((2+e)^n) = O(2^n)$ is as false a statement as $2+2=5$. However, usually exponential time encompasses $O(c^n)$ for any $c > 1$, so $O((2+\epsilon)^n)$ is already exponential time. $\endgroup$ Nov 18, 2014 at 14:59