Constant time describes a running-time bound that does not grow with the input size, provided relevant parameters remain fixed. In asymptotic notation, this is O(1). section 2.7.2 section 4.9.3
Treat an operation as constant time only after stating which quantities are independent of the growing input:
- A heap update costing O(log k) is O(1) when k is a fixed bound that does not depend on n. section 2.7.2
- Bloom-filter insertion takes O(k·T(|X|)); it becomes constant time for fixed k and keys whose lengths are bounded by a constant. section 4.9.3
- Variable-length strings do not automatically permit constant time: hashing remains dependent on string length unless a maximum length is fixed. section 4.9.3 section 4.9.4
- Constant time can be amortized, meaning occasional more expensive work is averaged across operations rather than bounded individually. section 7.4.3
Bounded Bloom-filter operations
An insertion computes k hash values and flips k bits. With fixed k and a fixed maximum key length, the work stays constant regardless of how many elements the filter already stores. Lookup has the same bounded behavior. section 4.9.3 section 4.9.4
Cache operations
An LRU cache can provide constant or amortized-constant storing, lookup, and eviction operations. An LFU cache implemented with a simple ordered list loses constant-time insertion and may require linear-time updates. section 7.4.3 section 7.5.2
Table 7.2 Comparative analysis of performance vs implementation for cache with n elements (view table figure)
| O(1) a |
O(1)a |
||||
| O(1)a |
O(1)a |
||||
| O(1)a |
Compare constant-time storing, lookup, and eviction across arrays, linked lists, hash tables, balanced trees, and LRU caches. section 7.4.3
