# Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

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!

• 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. – Yuval Filmus Apr 19 '16 at 16:12
• @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. – David Richerby Apr 21 '16 at 15:33