<p>Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a&lt;b, a&gt;b, a=b$ in constant time. </p>

<p>With this oracle for comparison, we can consider two data structures, of nodes, holding numbers, and pointers to each other:</p>

<p>Unordered Linked List:
Insertion $O(1)$
Search $O(n)$</p>

<p>Balanced Binary Tree: Insertion $O(\log n)$ , Search $O(\log n)$ </p>

<p>My question, do there exist data structures that carry an intermediary of running times between these? For example assuming that search takes $O(\sqrt{n})$ time what is the fastest insertion time, (does there exist a structure that supports $O(1)  \ \text{insert}$ or something more exotic such as $O(\log \log \log n)$)</p>

<p>The most general form of the question can be stated as:</p>

<p>Assuming insertion $O(\omega(n))$ , then how can we bound search time $s(\omega(n))$, and vice versa in the comparison model?</p>

<h2>Conjecture</h2>

<p>The tightest bound one can have is </p>

<p>Search:   $O( \frac{n}{\alpha(n)} + \log \alpha(n) ) $</p>

<p>Insert:  $ O (\log \alpha (n)) $</p>

<p>For choice of $\alpha(n)$ lying asymptotically between $O(1) ... O(n)$</p>

CC BY-SA 3.0
2016-07-14T18:16:17.367Z
The bounds you mention in the end can be matched by a hybrid between the two approaches you describe (at least with amortized insert cost): maintain a balanced binary search tree with <= k nodes in every node, stored as linked lists (for arbitrarily chosen k).
László Kozma
CC BY-SA 3.0
2016-07-14T18:33:42.997Z
Correct, that was motivation, But do we know if other stranger ways exist that beat these bounds? Or are these tight
Sidharth Ghoshal
<ds.algorithms><ds.data-structures><tree><asymptotics>
What is the curve of "search vs. insert"
Sidharth Ghoshal
# What is the curve of "search vs. insert"

(Asked by: username_0 on 2016-07-07)

Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $ab, a=b$ in constant time.

With this oracle for comparison, we can consider two data structures, of nodes, holding numbers, and pointers to each other:

Unordered Linked List:
Insertion $O(1)$
Search $O(n)$

Balanced Binary Tree: Insertion $O(\log n)$ , Search $O(\log n)$

My question, do there exist data structures that carry an intermediary of running times between these? For example assuming that search takes $O(\sqrt{n})$ time what is the fastest insertion time, (does there exist a structure that supports $O(1) \ \text{insert}$ or something more exotic such as $O(\log \log \log n)$)

The most general form of the question can be stated as:

Assuming insertion $O(\omega(n))$ , then how can we bound search time $s(\omega(n))$, and vice versa in the comparison model?

## Conjecture

The tightest bound one can have is

Search: $O( \frac{n}{\alpha(n)} + \log \alpha(n) ) $

Insert: $ O (\log \alpha (n)) $

For choice of $\alpha(n)$ lying asymptotically between $O(1) ... O(n)$

**Tags:** ds.algorithms, ds.data-structures, tree, asymptotics

> **Comments:**
> **username_1**: The bounds you mention in the end can be matched by a hybrid between the two approaches you describe (at least with amortized insert cost): maintain a balanced binary search tree with <= k nodes in every node, stored as linked lists (for arbitrarily chosen k).  
> **username_0**: Correct, that was motivation, But do we know if other stranger ways exist that beat these bounds? Or are these tight  

---

## 0 answers

