patternMinor
The Taylor series and time complexity analysis
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.
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.
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.