I have a function $f:\mathbb R^N\to \mathbb R$ and I would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input. What is the computational complexity using the (ones-sided) finite difference method $\big(\text{derivative of f w.r.t. x}\sim\frac {f(x+\epsilon)-f(x)}{\epsilon}\big)$ using the $O( \ )$-notation? Could you also provide an explanation of that?

  • 5
    $\begingroup$ You are dividing by a vector, aren't you? $\endgroup$
    – nicoguaro
    Commented Apr 5, 2020 at 14:19
  • 2
    $\begingroup$ Also, what is the complexity of evaluating $f$? $\endgroup$
    – nicoguaro
    Commented Apr 5, 2020 at 14:19
  • $\begingroup$ @nicoguaro why dividing by a vector? the complexity of f is not known but I suppose that does not impact on the general order of the complexity. Let's say that the general order is n, if $f$ embed a sum, a multiplication and some other computation, the order will be always n.. it seems to me.. $\endgroup$
    – Albert
    Commented Apr 5, 2020 at 20:11
  • 1
    $\begingroup$ @nicoguaro is right here. You are confused here I think. If $f$ is a function that takes a vector $x$, you can't evaluate this expression $\frac{f(x+\epsilon)-f(x)}{\epsilon}$ cause it seems $\epsilon$ is also a vector. Unless, you are also confused and mixed up the notations here, which needs to be clarified. Also, you can't say I don't care about time-complexity of $f$ cause any finite difference method to approximate the derivatives needs to evaluate $f$ at some points in the space and final time-complexity depends on $f$ for sure. $\endgroup$ Commented Apr 5, 2020 at 21:02
  • 1
    $\begingroup$ You meant to write $f(x+\epsilon e_i)$ where $e_i$ is the $i$th unit vector. $\endgroup$ Commented Apr 6, 2020 at 17:35

1 Answer 1


As pointed out in the comments, the cost of evaluating $f$ is critical, and in most practical cases will be the dominant cost. Lets suppose it takes $C$ operations to evaluate $f$. For nontrivial functions, $C$ will be at least $\mathcal{O}(N)$ just from using the $N$ arguments.

Also pointed out in the comments, the finite difference formula you have does not make sense for a function that maps a vector to a scalar. If you are looking to approximate the entire gradient vector $\nabla f$ with finite differences, you can use the approximation

$$ \nabla f(x) = \begin{bmatrix} \frac{f(x + \epsilon e_1) - f(x)}{\epsilon} & \frac{f(x + \epsilon e_2) - f(x)}{\epsilon} & \cdots & \frac{f(x + \epsilon e_N) - f(x)}{\epsilon} \end{bmatrix} + \mathcal{O}(\epsilon^2) $$

where $e_i$ is the $i$-th canonical basis vector for $\mathbb{R}^N$. There are $N+1$ calls to $f$ here along with $N$ subtractions and divisions so the cost is $\mathcal{O}(C N)$.

In many cases a gradient is multiplied by a vector to get a directional derivative $\nabla f(x) \cdot v$. If this is the case, the following approximation is more efficient:

$$ \nabla f(x) \cdot v = \frac{f(x + \epsilon v) - f(x)}{\epsilon} + \mathcal{O}(\epsilon^2). $$

Now there are just two function evaluations and a cost of $\mathcal{O}(C)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.