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