# Complexity of computing the antiderivative of a given function

Disclaimer: I don't know much computational complexity theory. I am nevertheless curious.

If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to measure), what can we then say about the computational complexity of the following indefinite integral?

$$\int f(x) \, \mathrm d x$$

For example, can we say something about how long it takes to approximate the integral of $f$ within an error of $\epsilon$, given that we know how long it takes to compute $f$ within an error of $\epsilon$?

• What do you mean by "the computational complexity of a function"? Is it complexity of an algorithm that computes the function $f(x)$? Dec 25, 2017 at 8:00
• @fade2black, yes I think thats what I mean, but since maybe sometkmes the integral cannot be computed (i dont know if thats true) lets say we require it to be computed within error $\epsilon$ Dec 25, 2017 at 9:17
• Is your model of computation RAM? Dec 25, 2017 at 9:24
• If $f$ polynomial? What error function are you using? Dec 25, 2017 at 9:50
• @YuvalFilmus, Why are you forcing me, a complete amateur, to choose a model of computation? My decision can only be random or ill informed. Doesn't it make a lot more sense for someone like yourself to choose the model based on what makes sense? I don't even know exactly what it means to choose a model of computation. I am just wondering whether, roughly, "all integrals of tractable functions are tractable". Dec 25, 2017 at 14:43

• You'll have to check the paper for the exact definitions, but generally speaking, in computable analysis, a "real number" is a machine that accepts a tolerance $\epsilon$ and returns a rational $\epsilon$-approximation to the number. For the definition of "real function" you'll have to check the paper. Dec 25, 2017 at 15:53