liveBook · Manning

Constant time

As explained in Algorithms Every Programmer Should Know

A time complexity, denoted O(1), that remains bounded independently of input size.

Suppose an array grows from ten numbers to ten thousand. Reading the number at a specified index is still one direct access. That is constant time, written O(1): the work for that operation does not grow with the array’s length. It does not mean every operation takes the same number of seconds. section 1.3.1

One access versus a search

If you know the index, read that position: O(1). If you must find a value by checking positions one by one, linear search can take O(N), where N is the array length. Swapping two numbers is another constant-time example. section 1.3.1

The same idea appears in several data structures and algorithms:

  • A stack pushes or pops at its top in O(1). A queue implemented with Python’s collections.deque supports O(1) operations. section 1.4.3
  • A hash map aims for near-constant-time insertion, retrieval, and deletion by hashing a key to an index. Collisions can make its worst case O(N). section 1.4.1
  • A rolling hash computes the next window’s hash in O(1) by updating the previous one. A completed all-pairs shortest-path matrix gives O(1) distance lookups, but takes O(V³) time to build. section 4.4 section 9.1

Always ask which operation the O(1) describes. A quick hash update does not make the entire pattern search constant time; a quick matrix lookup does not make building the matrix free. Speed can also require extra memory, as with hash maps and precomputed distances. section 1.4.1 section 4.4 section 9.1

Figure 1.2 A graph showing the time complexities with varying inputs. O(1) is the constant time, while O(n!) shows the worst time. O(log n) is logarithmic, and O(n) is linear time. Quadratic and cubic are in between and work well for smaller values of n.

Compare the flat O(1) line with curves that rise as input size increases. section 1.3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines O(1) through simple operations and qualifies hash-map performance with a worst-case collision scenario.
Examples
Uses indexed array access, swapping two numbers, and deque-backed queue operations.
What it assumes
Introduces time complexity using input size and basic array operations rather than assuming prior complexity analysis.
What you can do after
Evaluate/understand whether an O(1) claim applies to one operation or to a larger algorithm.
How it connects
Links constant-time operations to hash maps, stacks, and queues.

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 Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.