what is the time complexity of gradient $\nabla_{f}$ using the $\mathcal O$-notation? what is the time complexity of jacobian matrix using the $\mathcal O$-notation? who knows some references to introduce the time complexity of gradient? I make reply to reviewers for computational complexity of gradient and matrix operations. I need some references to cite.

  • $\begingroup$ For the numerical calculation of a 1D derivative at a single point, you require at least two points (left aside methods like the complex step-derivative). So that's O(1). You can carry that forward to higher dimensions and then to vectors and matrices. $\endgroup$ – davidhigh Oct 15 at 12:19
  • 1
    $\begingroup$ What algorithms are you using to compute your derivatives? Finite differencing? Automatic Differentiation (in forward or reverse mode)? How complicated is $f$? $\endgroup$ – Brian Borchers Oct 16 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.