Introduction

Asking for O(1) insertion and O(log n) search sounds reasonable at first, but the right answer depends on what “search” means. If you mean exact-key lookup, a hash table already gives average O(1) insertion and average O(1) search, which is better than O(log n).

If you mean ordered search such as predecessor, range lookup, or keeping elements sorted, the tradeoff changes completely. In that world, ordinary balanced trees give O(log n) insertion and O(log n) search, and you should not expect worst-case O(1) insertion at the same time.

Equality Search Versus Ordered Search

This distinction is the first thing to settle.

For equality search, a hash table is usually the correct structure:

1values = {}
2values[42] = "answer"
3values[7] = "lucky"
4print(values.get(42))

Insertion and lookup are both constant time on average.

For ordered search, you need the data to stay in some searchable order. That is why balanced binary search trees, skip lists, and B-trees pay O(log n) on insertion as well as search.

Why Arrays Do Not Meet the Goal

A sorted array has fast binary search but slow insertion because elements must move to make space.

1import bisect
2
3nums = [1, 4, 7, 10]
4index = bisect.bisect_left(nums, 7)
5print(index)
6
7bisect.insort(nums, 6)
8print(nums)

The search for the insertion point is O(log n), but inserting into the list is still O(n) because the tail shifts.

That is the pattern behind many “almost right” answers: one operation is cheap only because another operation pays the bill.

What You Can Actually Use

Choose the structure based on the real requirement.

If you need exact lookup only:

• hash table or hash set
• average O(1) insert
• average O(1) search

If you need ordered queries:

• balanced BST, skip list, or B-tree
• 'O(log n) insert'
• 'O(log n) search'

If you need very fast writes and can tolerate amortization or background merging:

• buffered trees or LSM-style designs
• inserts can be very cheap in practice
• search becomes more complicated and usually spans multiple levels

That last category is how storage engines approach the problem. It is not the same as exact worst-case O(1) insertion with clean O(log n) search in a simple in-memory structure.

A Practical Compromise

One compromise is a hash table for membership plus a sorted structure for ordered operations. That gives different complexity for different kinds of questions.

1import bisect
2
3class HybridSet:
4    def __init__(self):
5        self.lookup = set()
6        self.sorted_values = []
7
8    def add(self, value):
9        if value in self.lookup:
10            return
11        self.lookup.add(value)
12        bisect.insort(self.sorted_values, value)
13
14    def contains(self, value):
15        return value in self.lookup
16
17    def lower_bound(self, value):
18        i = bisect.bisect_left(self.sorted_values, value)
19        return self.sorted_values[i] if i < len(self.sorted_values) else None
20
21
22h = HybridSet()
23for value in [10, 4, 7]:
24    h.add(value)
25print(h.contains(7))
26print(h.lower_bound(6))

This is useful, but notice the insertion is no longer O(1) because the sorted list still has to maintain order.

The Conceptual Lower Bound

For ordinary comparison-based ordered structures, maintaining enough order to support logarithmic search generally means paying logarithmic work on updates too. That is why red-black trees, AVL trees, skip lists, and B-trees all cluster around the same complexity.

So if someone asks for a general-purpose data structure with worst-case O(1) insertion and O(log n) ordered search, the honest response is usually: not in the standard model you probably mean.

Common Pitfalls

A common mistake is saying “hash table” without checking whether ordered queries are needed. Hash tables are excellent for equality lookup and poor for ordered traversal.

Another mistake is confusing the search for the insertion position with the cost of insertion itself. In arrays and Python lists, finding the slot can be O(log n) while inserting remains O(n).

People also mix worst-case and average-case bounds. Hash tables are usually described with average O(1) operations, not strict worst-case guarantees.

Finally, do not design around asymptotic notation alone. Constants, cache behavior, and query patterns often matter more than one letter in the complexity expression.

Summary

• First decide whether “search” means equality lookup or ordered search.
• For equality lookup, hash tables usually give better than O(log n) on average.
• For ordered search, balanced trees and similar structures give O(log n) insertion and search.
• A simple in-memory structure with worst-case O(1) insertion and general ordered O(log n) search is not the normal outcome in the comparison model.
• Pick the data structure that matches the actual query pattern instead of chasing a complexity pair in isolation.