Sorry if this is too simple. This is my first question here.


Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point $x$. Can we use that to somehow precisely bound the time that is required to compute $\nabla f$? (Intuitively because of finite difference approximations, we might be able to do this, but is a precise statement available, or am I overlooking something obvious?)



Complexity of computing derivatives
The complexity is $O(nT)$. Look up "automatic differentiation" in Wikipedia. This is taking your statement about computing $f(x)$ in $T$ arithmetic operations literally: the "arithmetic operations" could include arbitrary powers and elementary functions such as exp, ln, sin, considered as single operations, as long as their derivatives can also be computed with a bounded number of operations. If approximations and errors must be taken into account, that's a whole different story.


