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

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.

• I suggest this paper of Shallit Apr 4, 2020 at 17:31
• What "time complexity analyses" by Lagrange do you have in mind? Apr 4, 2020 at 21:08

"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."