On the oracle complexity of first-order and derivative-free
                algorithms for smooth nonconvex minimization

                 C. Cartis, N. I. M. Gould and Ph. L. Toint

                         Report NAXYS-03-2010

The (optimal) function/gradient evaluations worst-case complexity analysis
available for the Adaptive Regularizations algorithms with Cubics (ARC) for
nonconvex smooth unconstrained optimization is extended to finite-difference
versions of this algorithm, yielding complexity bounds for first-order and
derivative free methods applied on the same problem class. A comparison with
the results obtained for derivative-free methods by Vicente (2010) is also
discussed, giving some theoretical insight on the relative merits of various
methods in this popular class of algorithms.