When did the study of the rate of convergence of algorithms begin?

Question

I was reading a book about computational complexity theory and the author made a claim that the study of time complexity of algorithms started with a result on the upper bound on the number of operations needed by euclid's algorithm on two numbers by Gabriel Lamé in the early/mid 1800s. Since analyses of speed of convergence of algorithms can also be thought as sort of proto-time complexity analyses and date back at least to Lagrange I was wondering if they are even earlier than Lagrange.

Answer 1

Rate of convergence estimates are typically not counted as estimating complexity of algorithms because the relation between number of steps in them and computational complexity is not very straightforward. And the algebraic analysis conceptions of 18th century make comparisons to the modern complexity theory even more remote, see Was 18th century algebra more symbolic/formal than the modern conception? This is likely why its origins are only traced to the work of Reynaud (1811), Finck (1841) and Lame (1844) on the Euclidean algorithm, where both issues are absent.

However, both the rate of convergence and its speed up were commonplace in the investigation of series in the early 18th century, albeit not in the way resembling the modern one. Ferraro has two papers Convergence and Formal Manipulation of Series from the Origins of Calculus to About 1730 and Convergence and formal manipulation in the theory of series from 1730 to 1815, on the subject.

For example, Jacob Bernoulli explicitly introduced and estimated remainders for the geometric series and the Mercator method in Ars Conjectandi (1713). But these sorts of considerations happily coexisted with the formal conception of series and manipulating divergent series, which got him in trouble with the "sum" of inverse square roots. Attempts to improve rates of convergence themselves often involved formal manipulations, and led to the appearance of divergent asymptotic series, as in Stirling's Methodus Differentialis (1730). Even d'Alembert, who criticized the use of divergent series and made detailed rate of convergence estimates for the binomial series in Réflexions sur les Suites et sur les Racines Imaginaires (1768), was no exception.

"Although N. Bernoulli's and d'Alembert's conception might seem close to modern ideas about series, it was in fact rather problematic... I stress that d'Alembert accepted the principle of formal manipulation upon which the early theory was based: this was precisely the principle that had led to asymptotic series, recurrent series, etc. In particular, d'Alembert did not consider series as autonomous objects but the result of transformations of given closed analytical expressions. Although it is true that d'Alembert used the inequality technique, it was only a tool for the numerical evaluation of a function. In no case was this technique used to prove the existence of a limit. D’Alembert had no knowledge of the ratio test, if by this term we refer to a criterion to establish whether a given series has a finite sum or not. For him the condition $a_{n+1}/a_n < 1$ served to establish where the series approximated its known sum: the “ratio test” was not used to prove the existence of the sum but was only a procedure to determine the bounds of errors. In conclusion, criticisms of the use of divergent series were weak because all mathematicians used formal procedures even if some of them, such as Euler, Lagrange, and Laplace, used them in a stronger form."

This said, Lagrange did publish two long papers on the numerical solution of equations in 1769/70, and continued to work on the subject with his work eventually summarized in his book Traite de la Resolution des Equations Numeriques de Tous les Degres (1798, revised 1808). There is also a chapter on them in his Lectures on Elementary Mathematics, translated into English. He paid special attention to the rate of convergence and accelerating it, both for series and continued fractions. In particular, he replaced Newton's method with a continued fractions based one that provided error estimates, and introduced generalized continued fractions to speed up the convergence, see Lagrange and the Solution of Numerical Equations by Laubenbacher and McGrath.