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?)
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.
With all due respect to Mr. Israel, his answer is incomplete and, I must apologize writing this, misleading. Let $f: \mathbb{R}^n \to \mathbb{R}^m$ so that the Jacobian $f'(x)$ is a $n \times m$ matrix for every $x$. Assume that $f(x)$ takes $T$ arithmetic operations to evaluate. Fix $x \in \mathbb{R}^n$.
Forward AD evaluates $f'(x)$ in $O(1)Tn$ arithmetic operations.
Reverse AD evaluates $f'(x)$ in $O(1)Tm$ arithmetic operations.
In your case, $m=1$ so the reverse mode evaluates $f'(x)$ in $O(1)T$ operations. This reverse mode AD is also known as "backpropagation" in machine learning, and is a key business strategy for several trillion dollar companies.
The $O(1)$ term was estimated by some illustrious mathematician, I apologize I can't find the reference now, but it's something like $O(1)=3$. So it's something like $3T$ arithmetic operations; barely more than what is needed to compute $f(x)$.
