13
$\begingroup$

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?

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

Improve this question
$\endgroup$
2
  • 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$
    – László Kozma
    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$
    – Sidharth Ghoshal
    Jul 14, 2016 at 18:33

0

Reset to default

Your Answer

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