HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

The Taylor series and time complexity analysis

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thetayloranalysistimeandseriescomplexity

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#65903, answer score: 6

Revisions (0)

No revisions yet.