Constant time
Constant time is an asymptotic complexity in which the running time remains bounded independently of input size, conventionally denoted O(1).
Fabulous Adventures in Data Structures and Algorithms
Constant-time complexity is computational complexity in which an operation takes a bounded amount of time independent of input size.
- How it is used
- Distinguishes the costs of individual operations from whole algorithms and sequences of operations.
- How deep it goes
- Defines O(1) and contrasts worst-case, amortized, and deferred costs, without deriving formal bounds.
- Examples
- Uses queue operations, Hughes-list reversal, and Fisher–Yates swaps to contrast constant and linear costs.
- What you can do after
- Evaluate operation costs by distinguishing worst-case bounds, amortized bounds, and deferred work.
Read how Fabulous Adventures in Data Structures and Algorithms explains constant time →
Practices of the Python Pro
Constant time is an asymptotic performance classification in which execution time remains bounded independently of the number of inputs.
- How it is used
- Frames constant time as a target for analyzing and designing high-performance software.
- How deep it goes
- Defines O(1), explains upfront-computation trade-offs, and distinguishes constant-time lookup from O(n) iteration.
- Examples
- Uses Python dictionaries, sets, lists, and a favorite-colors file to contrast constant-time operations with linear work.
- What you can do after
- Apply it via Python dictionaries and sets to make repeated item access or membership checks independent of input size.
Read how Practices of the Python Pro explains constant time →
Advanced Algorithms and Data Structures
Constant time is a running-time bound independent of the input size, up to a fixed bound.
- How it is used
- Uses constant-time bounds to compare data-structure operations and justify performance choices under explicit parameter assumptions.
- How deep it goes
- Defines O(1) through heap, hashing, key-length, and amortization cases, but stops short of formal proofs.
- Examples
- Uses bounded heap updates, Bloom-filter insertion and lookup, LRU-cache operations, and inefficient LFU-list updates as examples.
- What you can do after
- Evaluate whether an operation is O(1) by identifying growing inputs, fixed bounds, key-length limits, and amortization.
Read how Advanced Algorithms and Data Structures explains constant time →
Clojure: The Essential Reference
Constant time is an asymptotic complexity in which execution time does not grow with input size.
- How it is used
- Characterizes fixed-cost function creation, invocation, bitwise operations, and lazy-sequence generation.
- How deep it goes
- Distinguishes setup from consumption, invocation arity, hardware dependence, caching, and retained-head memory costs.
- Examples
- Uses fnil, bitwise operations, powerset generation, repeatedly, random values, and a large lazy sequence.
- What you can do after
- Evaluate complexity claims by separating eager setup, deferred consumption, supported arity, and retained data.
Read how Clojure: The Essential Reference explains constant time →
Latency
Constant time is an algorithmic growth class in which required operations remain independent of input size.
- How it is used
- Uses growth classification to guide low-latency algorithm choices and identify work worth eliminating.
- How deep it goes
- Defines O(1), contrasts growth classes, and distinguishes average from worst-case lookup behavior without deriving implementation internals.
- Examples
- Uses linear array search, hash-table lookup, a growth comparison figure, and an operations-complexity table.
- What you can do after
- Evaluate algorithm choices by separating growth behavior, absolute runtime, average cases, and worst-case cases.
Python Workout: 50 ten-minute exercises
An asymptotic time complexity that remains bounded independently of the number of elements processed.
- How it is used
- Frames constant time as a way to reason about dictionary and hash-based lookup performance.
- How deep it goes
- Explains bounded growth through an office analogy and dictionary mechanics, while acknowledging collisions without detailing their implementation.
- Examples
- Uses alphabet-indexed office searches and Python dictionary retrieval to illustrate constant-time access.
- What you can do after
- Evaluate whether direct lookup remains bounded as the collection grows, including the effect of collisions.
Read how Python Workout: 50 ten-minute exercises explains constant time →
Python Workout, Second Edition
Constant time is a computational complexity in which execution time does not grow with the size of the input.
- How it is used
- Frames constant time as the performance characteristic motivating hash-based lookup and Python dictionaries.
- How deep it goes
- Defines O(1), illustrates its scaling behavior, and sketches hashing and collisions while deferring several implementation details.
- Examples
- Uses numbered offices, alphabetic initials, duplicate surnames, and d['a'] = 1 to demonstrate direct lookup and collisions.
- What you can do after
- Apply it via Python dicts by relating key hashing to immediate storage-slot lookup and recognizing collision handling.
Read how Python Workout, Second Edition explains constant time →
Related concepts
- hash mapmeasured by · A hash map is a key-value data structure that uses a hash function to locate entries and support efficient lookup, insertion, and removal by key.
- Mapmeasured by · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
- performancekind of · Performance is the measurable effectiveness or operational behavior of a system under specified conditions, assessed through relevant qualities such as task results, speed, responsiveness, throughput, or resource use.
- lookup operationmeasures · A lookup operation locates or retrieves data associated with a specified key, identifier, index, or other locating value.
- setused by · A set is a collection of unique elements in which membership is determined by whether an element is present, not by duplicate occurrences.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.