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?ConjectureThe 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)$
What is the curve of search vs. insert
ds.algorithms;ds.data structures;tree;asymptotics