Return to Revisions

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.