Limitation of a data structure


I must give credit to my favourite professor sundar for this problem.

Problem : Let there be an abstract data structure D. D is a k-Max data structure, in a sense that on performing delete() on this data structure, it returns the k-th largest(Maximum ) element of the elements stored in it. Only two operations are allowed on D, insert(number) and delete(). Obviously, insert(n) will insert the given number n to the data structure.

Prove that, it is impossible to implement D in a way such that both insert(n) and delete() takes O(1) time. Or in other words, any implementation of D will have at most one operation that can perform in O(1). The other operation can not be implemented in O(1).

On sujith‘s request, I am giving a bit more space between the problem definition and solution so that one can avoid accidental peeking :-).

Solution : If someone want a bit of a hint, I would say, the proof goes by contradiction. If ,indeed, we have one such data structure we will defy rules of computational complexity.

Let us assume that we have such a data structure D. and let k=1, that is D is a 1-max data structure, which returns the largest element in D. Also, assume that insert(n) and delete() are both O(1) operations. Now, if I am given n integers. I would insert them one by one. After all insertions I will perform deletions. It is easy to see that this way, I can sort n integers in time O(n)!!!!

It should be fairly easy to see why this is true for any value of k>0. In linear time we can find the largest, say Max, of n integers. I can insert (k-1) dummy integers which are greater than Max in D. And again, I have a linear time sorting algorithm in the worst case!!!

It is a clear contrast to logarithmic lower bound for sorting.

Now we know why we don’t have any such data structure 🙂

— Saurabh Joshi


Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: