Constant Time Computation (Designing O(1) Solutions)

O(1) means the work does not grow with input size for that step—hash map lookup, deque ends, or a fixed formula. Whole programs are rarely O(1); you isolate the hot step that must stay flat.

Why this shows up in the real world

CPU caches assume pointer-chasing stays shallow. Rate limiters use O(1) token buckets per request.

Core idea (explained for students)

Use dict/set for membership, store running aggregates instead of recomputing sums, precompute powers in modular exponentiation tables when the exponent pattern is fixed.

Try this in Python

def o1_lookup(freq: dict[int, int], x: int) -> int:
    return freq.get(x, 0)


print(o1_lookup({1: 5, 2: 3}, 1))

Common mistakes

• Calling len(list) inside a tight loop that grows the list—still linear overall.
• O(1) amortized structures (dynamic array append) reported as strict O(1) worst case incorrectly.

Key takeaways

• Label costs per operation vs whole algorithm clearly in writeups.
• Prefer deque over list for queue ends when pops happen at front.