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?

  • 3
    $\begingroup$ What is your computation model? The cell probe model, perhaps? $\endgroup$ Commented Apr 19, 2016 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$ Commented Apr 19, 2016 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$ Commented Apr 19, 2016 at 16:12
  • 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$ Commented Apr 21, 2016 at 15:33
  • 1
    $\begingroup$ @jbapple, sounds like an answer! Maybe write an answer here describing the lower bound (that's relevant to this problem) and citing that paper? This question does look different, even if that paper is relevant to this question too. $\endgroup$
    – D.W.
    Commented Apr 21, 2016 at 22:46


Your Answer

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

Browse other questions tagged or ask your own question.