# Time complexity of numerical finite differences

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?

• You are dividing by a vector, aren't you? Apr 5 '20 at 14:19
• Also, what is the complexity of evaluating $f$? Apr 5 '20 at 14:19
• @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.. Apr 5 '20 at 20:11
• @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. Apr 5 '20 at 21:02
• You meant to write $f(x+\epsilon e_i)$ where $e_i$ is the $i$th unit vector. Apr 6 '20 at 17:35

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)$$.