Time complexity of numerical finite differences

Question

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?

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