3
$\begingroup$

I was just wondering, if an algorithm $A$ has a time complexity O$(2^n)$, since $2^n$ can be represented using a Taylor series, which is a polynomial, does this mean that $A$ has polynomial time complexity? Generalising even further, does this mean that any algorithm which has a time complexity O($f(n)$) where $f(n)$ has a corresponding Taylor series representation is also a polynomial time algorithm?

Thanks very much in advance.

$\endgroup$
  • $\begingroup$ If you define the term "polynomial" to include polynomials with unbounded degree (and thus infinite terms) then yes... but that's not usually the case. $\endgroup$ – Bakuriu Nov 12 '16 at 8:51
5
$\begingroup$

$2^n$ can be represented as a Taylor series, which is an infinite sum of polynomials. Notably, there is no single polynomial which is equal to $2^n$.

In general, since big-O lets us get rid of lower-degree terms in the polynomial, we can say that something has polynomial time (or space or whatever you're measuring) when it is $O(n^k)$ for some fixed $k$.

Since there's no single $k$ where $\forall n \ldotp O(2^n) = O(n^k)$, we say that $2^n$ is not polynomial.

$\endgroup$
4
$\begingroup$

Your mistake is that you are confusing Taylor series and Taylor polynomial. $2^n$ can be represented as a Taylor series, which is an infinite series of polynomials (that is the limit of an infinite sequence of polynomials). When you cut off a Taylor series at some fixed degree, you get a Taylor polynomial, which is a polynomial. However, $2^n$ cannot be reasonably approximated by any polynomial, including a Taylor polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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