Linear memory complexity, written O(n), means memory requirements grow in proportion to the number of input items. It is a useful warning when a collection or result set may be too large to hold comfortably in memory. The bound describes growth, not a fixed memory amount. section 8.3.5 section 9.3.7
Clojure's sort and sort-by use Timsort, which allocates O(n) memory and takes O(n log n) steps in the worst case. Sorting a small collection is usually unremarkable; sorting a large one merits a performance review. The time and memory bounds answer different questions: how much work sorting takes, and how much space it needs. section 8.3.5
A small sort
(sort [:a :z :h :e :w]) ;; (:a :e :h :w :z) The result is straightforward, but the same operation on a much larger collection still carries a linear memory requirement. For data fetched in chunks, psort instead sorts chunks and lazily merges them; unless its entire result is realized, it need not load the entire dataset into memory. section 8.3.5
For sequence adapters, distinguish worst-case space from what an incremental consumer retains:
- resultset-seq has O(n) worst-case memory. Large JDBC results can be processed incrementally with reduce if the driver streams rows, the processing function does not need them all, and the caller does not retain the sequence head. section 9.3.7
- iterator-seq and enumeration-seq also have O(n) worst-case memory when fully consumed. Both are lazy, but iterator-seq advances in chunks of 32 items, whereas enumeration-seq is fully lazy. section 9.3.8
The practical question is not just whether an API is lazy. Check whether it must arrange all input, whether the underlying source truly streams, and whether the consumer holds on to realized values. section 8.3.5 section 9.3.7
