Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different f

Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different from) computational complexity theory / theory of algorithms. Robert Sedgewick (CS professor at Princeton, and an early PhD student of Knuth) has a great book with Flajolet on Analysis of Algorithms [1], and in one of the lectures from his course [2] makes a distinction between the complexity analysis usually taught in basic undergraduate algorithms courses (he calls O-notation not the scientific method, in a certain context in the lecture) and AofA (which involves saying "Running time is ~aN^c" instead of saying "Running time is O(N^c)", and also actually measuring against real programs) — watch the video or read the slides; it's an interesting distinction. And the Purdue website [3] is even better at giving a sense of the field. [1]: https://aofa.cs.princeton.edu https://aofa.cs.princeton.edu [2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lecture/LAXjA/a-scientific-approach https://www.coursera.org/learn/analysis-of-algorithms/lectur... [3]: https://aofa.cs.purdue.edu https://aofa.cs.purdue.edu