Constant time, written O(1), describes an operation whose execution time does not grow with input size. It is useful for distinguishing fixed-cost setup from work performed later or repeatedly. section 2.2.1 section 9.2.1
Clojure examples show three different meanings of an O(1) claim:
- fnil generates a defaulting function in constant time, and invoking that generated function is also constant time when limited to its supported arities. section 2.2.1
- Bitwise operations are practically constant time; dependencies on the number of bits are generally hardware-dependent and insignificant for ordinary use. section 3.2.3
- repeatedly creates a lazy sequence in constant time, but fully consuming it takes O(n), and retaining its head can require O(n) memory. section 9.2.1
Constant setup does not mean constant total work
(let [rands (repeatedly 10000000 rand)] (first rands) (last rands)) ;; first access is immediate; later consumption performs the requested work (repeatedly generates the lazy sequence in O(1), while requesting items grows work and cached memory with n.) section 9.2.1
