Is gradient descent slower for finite differences?
(In response to the comments)

Consider logistic regression with labels +1/-1, where the function is $f(x) = \sum log(1 + \exp(-y * (x \theta)))$ . Taking finite differences requires computing $\sum log(1 + \exp(-y * (x (\theta + \epsilon_n))))$ (where $\epsilon_n$ is a small value for only one variable) for each variable (in each evaluation, you require plugging in the current values of all other variables too). The analytical solution is $\sum residual \theta$ - you only require plugging in the current values twice. You can keep a sum of $\theta x$ to save calculations (still more calculations with the differences approach), but as your function gets more non-linear, there’s less that you can precompute between variables – e.g. if you have 3 hidden units, changing the first unit will not let you reuse computations for the others.

In terms of big-oh notation, if you are looking at number of evaluations and you consider the gradient evaluation as $O(n)$ (keep in mind vectorization makes a difference though), I guess you won’t see much difference, but if you look at others aspects you’ll see that the analytical solution requires fewer calculations.

In addition, optimization techniques such as L-BFGS will not work if you don’t use precise gradients.