4
$\begingroup$

How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at most $\mathcal O(\log\log n)$? (For clarity, I am considering equality == and inequality < tests to be the only "costly" operations and considering things like dereferencing pointers to have negligible cost.)

My attempt so far is as follows. We can design a kind of "hybrid" data structure that consists of an (unordered) linked list of binary trees such that as we continue adding elements, the number of nodes in each binary tree grows asymptotically to some function $s(n)$, and the number of trees in the list grows asymptotically to $n/s(n)$, where $n$ is the total number of elements. Inserting new elements in this structure will have a worse-case complexity of $\log(s(n))$ in the long run, and looking up elements will have a worst-case complexity of $(n/s(n))\cdot \log(s(n))$ if we iterate through the trees one by one and employ binary search on each tree until we find the desired element. This general method gives us $$I(n) = \Theta\big(\log s(n)\big), ~ ~ ~ L(n) = \Theta\big(\frac{n\log s(n)}{s(n)}\big)$$ where $I(n)$ measures insertion complexity and $L(n)$ measures lookup complexity. Fixing an exponent $p>0$ and choosing $s(n) = (\log n)^p$ gives us the desired maximum insertion time of $\log\log n$, and a lookup time of $$L(n)=\Theta\big(\frac{n\log\log n}{(\log n)^p}\big)$$ so we can conclude that this lookup complexity is achievable for any $p>0$ in a way that satisfies the constraint $I(n)=\mathcal O(\log\log n)$.

Can we do better than this? For instance, can we achieve, say, a lookup time of $L(n)=\mathcal O(n^{1-\epsilon})$ for some $\epsilon > 0$ while still meeting the $I(n) = \mathcal O(\log\log n)$ insertion requirement? (My intuition tells me the answer is "no".) Are there any applicable strategies for proving that the best possible complexity has been found?

$\endgroup$
5
  • 1
    $\begingroup$ Since hashtables achieve insertion and lookup in $\mathcal{O}(1)$ average case, I assume that you are only interested in worst case? $\endgroup$
    – Nathaniel
    Commented Nov 23, 2022 at 21:42
  • $\begingroup$ @Nathaniel Yes, sorry! I should have specified, I'm only looking at worst-case times. $\endgroup$ Commented Nov 23, 2022 at 21:48
  • 1
    $\begingroup$ Maybe related? stackoverflow.com/questions/40438332/… $\endgroup$
    – Nathaniel
    Commented Nov 23, 2022 at 22:29
  • $\begingroup$ @Nathaniel That question has an interesting answer, but I'm not looking for an answer that will reduce the cost to O(1) by assuming something about the data (say, that a datum consists of 32 bits). Rather, I'm looking for something that works for any kind of data that can be ordered/compared, with constraints placed on the (asymptotic) number of comparisons. The problem would trivially become O(1) for both search and insertion anyways if the number of possible data was finite (using a table). $\endgroup$ Commented Nov 24, 2022 at 11:01
  • $\begingroup$ en.wikipedia.org/wiki/Van_Emde_Boas_tree $\endgroup$
    – Pseudonym
    Commented May 22 at 4:23

1 Answer 1

1
$\begingroup$

After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning in this blog post draft.

As a TLDR, by using some combinatorial results about posets, we can show that if the hidden constant in the insertion complexity is less than some $C > 0$, then the lookup complexity can be at best $$\Theta\bigg(\frac{n}{(\log n)^C}\bigg)$$ On the other hand, it's possible to design a data structure that actually achieves $\mathcal O(\log \log n)$ insertion complexity and the above lookup complexity for any value of $C > 0$. This implies that for any data structure satisfying the constraint, one can obtain another data structure with strictly better lookup complexity by increasing the value of the hidden constant.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.