When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be computed incrementally, or "online", in O(1) space. That is, if the data were a stream we could compute the statistic without needing to store every previously seen item.
However, for computing the median O(N) space is required. There is no way to compute the median in a "rolling" fashion without maintaining all values in memory.
My question is, do these different classes of functions have a classification to describe them (beyond simply saying O(1) or O(N) space)? If I wanted to find more functions like median that require all elements to be present in memory to compute, what would I search for?