constant time
Work that stays the same no matter how large the input is, written O(1).
In more detail
Reading a list element by index, pushing onto a stack and looking up a key in a dict are all constant time on average. Constant does not mean instant; it means the cost does not depend on n. A dict lookup among ten items and among ten million items costs about the same.
Related terms
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
- hash table — A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers