29 ms·

What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exi

What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exists a huge literature that studies algorithms under various models of the memory hierarchy, and under various models of I/O. Even Knuth's venerable The Art of Computer Programming from 50 years ago studied the problem of optimal sorting assuming that the data is on tape and one has six tape drives available (for some value of six that I forgot).

svat 5y ago
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

svat 5y ago

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