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).
This has been copied from Saurabh Joshi's blog. He acknowledges Prof. Sundar (CSE, IITB) for the problem. :)
Highlight the part between the * symbols for the answer.
* 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)!!!!