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.