liveBook · Manning

Constant time

As explained in Latency

Constant time is an algorithmic growth class in which required operations remain independent of input size.

Constant time, written O(1), describes an algorithm whose runtime remains the same as input size n grows. Big O compares growth rather than absolute execution time, so an O(1) operation is not necessarily faster for every small input. section 7.2

Constant-time choices matter in latency-sensitive code because replacing work that grows with n can prevent runtime from increasing rapidly. A hash table lookup is O(1) on average, while collisions can require a linear scan and produce O(n) worst-case behavior. section 7.2

Comparing lookup strategies

A linear search may inspect every element when the target is last, requiring O(n) steps. A hash table provides average O(1) lookup, but its operation must still be evaluated against worst-case behavior and input size. section 7.2

Figure 7.1 Illustration of algorithmic complexity in big O notation for constant time 𝑂(1), logarithmic time 𝑂(log𝑛), linear time 𝑂(𝑛), and quadratic time 𝑂(𝑛2)
Figure 7.3: Illustration of algorithmic complexity in Big O notation for constant time O(1), logarithmic time O(log n), linear time O(n), and quadratic time O(n^2).

Compare how constant, logarithmic, linear, and quadratic runtimes grow as input size increases. section 7.2

How Latency covers it

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.
How it connects
Connects constant time with Big O notation, linear search, hash tables, collisions, and algorithmic complexity.

Also explained in

Compare how 8 books explain constant time →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Latency. The section links point to the parts of the book it draws on.