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?

  • $\begingroup$ Note that there is an active research area - "data stream algorithms" - concerned with finding approximate answers to different statistic queries using highly sublinear space and time-per-item. $\endgroup$ – jkff Dec 1 '14 at 7:42
  • 1
    $\begingroup$ Mean/min/max really use logarithmic space, since you need that much space to store non-constant integers. Especially in the case of mean, even if the numbers are constant-size, you still need $O(\log n)$ bits to store the sum of $n$ constant-size numbers. I'd argue that $L$ (logspace) is the most natural complexity class for mean/min/max, but sadly it also contains the median problem (since it can be computed with $O(\log n)$ additional space and $O(n \log n)$ time. So you'd want to extend the definition of $L$ with a read-once constraint but that class hasn't been studied much (or at all). $\endgroup$ – Tom van der Zanden Dec 1 '14 at 10:11
  • $\begingroup$ @TomvanderZanden, thanks for the correction on O(log N) space for the mean/min/max. That makes sense. Can you elaborate on what you mean by an O(log N) additional space for the median though? If the computation needs all N numbers to compute the median and each number takes log n bits, wouldn't the total space be O(N log N)? Also, why did you say O(N log N) time complexity? Can't the median could be computed in O(N) time using QuickSelect? Thanks for helping me understand. $\endgroup$ – Steve Dec 1 '14 at 10:48
  • 1
    $\begingroup$ Indeed, quickselect allows $O(n)$, I'm not sure how I came up with $O(n \log n)$. I said "additional space", so it gets to use (read-only) $O(n)$ (or $O(n \log n)$ if you want to be precise) space from which it can read the input, and $O(log n)$ (read/write) space to do the calculation. That ($O(log n)$ additional space) is the definition of $L$, which is why I suggested you need to extend the definition with some kind of read-once constraint. Mean/min/max also need $O(n \log n)$ space to store all the numbers, but they only read them once whereas quickselect may need to read them more often. $\endgroup$ – Tom van der Zanden Dec 1 '14 at 10:54
  • 1
    $\begingroup$ Also, another thought with regards to quickselect: if you only allow $O(log n)$ additional space, the $O(n)$ time bound may no longer apply (since this requires reordering the numbers). But you can definitely compute the median with $O(n^2)$ time and $O(\log n)$ additional space. $\endgroup$ – Tom van der Zanden Dec 1 '14 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.