Complexity of computing derivatives - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:06:21Z http://mathoverflow.net/feeds/question/73596 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73596/complexity-of-computing-derivatives Complexity of computing derivatives onemoreuser 2011-08-24T18:45:24Z 2011-08-24T21:58:54Z <p>Sorry if this is too simple. This is my first question here.</p> <p>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?)</p> http://mathoverflow.net/questions/73596/complexity-of-computing-derivatives/73602#73602 Answer by Robert Israel for Complexity of computing derivatives Robert Israel 2011-08-24T19:29:57Z 2011-08-24T21:58:54Z <p>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.</p>