When your data doesn’t fit in memory: the basic techniques
Unusual to have no occurrence of the word "stream" anywhere in the article... given that's the usual term for algorithms which require a constant or almost-constant space regardless of the amount of data they process.A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space.