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<b, a>b, 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?


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)$

  • 2
    $\begingroup$ 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). $\endgroup$ Jul 14, 2016 at 18:16
  • $\begingroup$ Correct, that was motivation, But do we know if other stranger ways exist that beat these bounds? Or are these tight $\endgroup$ Jul 14, 2016 at 18:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.