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. If approximations and errors must be taken into account, that's a whole different story.
Robert Israel
- 54.2k
- 1
- 76
- 152