5
$\begingroup$

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$.

Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but getting the $k$-th largest element costs $O(\log{N})$.

I can't think of any way to create a data structure with the best of both worlds, that is that we can get the $k$-th largest element in $O(1)$, and insertions and deletions cost only $O(\log{n})$, but I can't prove that it isn't possible.

So far, my idea for a proof basically revolves around it being impossible to have $O(1)$ accesses without an array. We can't have a tree or a linked list without the time complexity becoming dependant on the number of elements. Then, if an array is required, the only way to insert an element in less than $O(\log{n})$ time is to add it to the end or to the front (which is $O(1)$). But if we do this, we can't maintain the sorting of the list. So we need another data-structure which maps a given $k$ to its real index in the array in $O(1)$ and which supports insertions/deletions in $O(\log{n})$. The only difference between this inner data structure and the outer one is that the elements in the inner array will be each number from $0$ to $n$, but I don't think that matters and now I'm just back where I started!

What's the answer?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ What is your computation model? The cell probe model, perhaps? $\endgroup$ – Yuval Filmus Apr 19 '16 at 15:46
  • $\begingroup$ Thanks for the comment! Unfortunately, I'm not familiar with models of computation and I only have a basic understanding. A brief reading leads me to believe that a model of computing defines what is considered an operation. In this case, I would consider each time that the state of the computer changes to be an operation. But since I obviously don't know what I'm talking about, feel free to use any reasonable model you like! $\endgroup$ – AStupidNoob Apr 19 '16 at 16:10
  • 1
    $\begingroup$ The usual model in these cases is the cell probe model. This implies that you can do precomputation on $k$ for free, for example, as long as you don't look at the data structure. Another reasonable model is the comparison model. $\endgroup$ – Yuval Filmus Apr 19 '16 at 16:12
  • $\begingroup$ What's the relationship between $k$ and $n$? Is $k$ a constant? When you write $O(1)$, do you mean that the time doesn't depend on $n$; or also that it doesn't depend on $k$? I suspect these subleties might affect the answer. For instance, if $k$ is a constant (so we're willing to consider $k=O(1)$), then I think there does exist such a data structure. $\endgroup$ – D.W.♦ Apr 19 '16 at 17:54
  • 1
    $\begingroup$ @jbapple I don't see how that follows. The asker here isn't trying to do better than $O(\log n)$ for insertions and deletions, and the operation of $k$-th largest isn't mentioned by the other question. $\endgroup$ – David Richerby Apr 21 '16 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.