2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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