[Solved] How to design a data structure which supports the following operations in constant time?

by


Suppose such a data structure existed.

Then here is an O(n) comparison-based sorting algorithm:

  1. Push() every item into this data structure.
  2. Pop() them all off in sorted order.

No O(n) comparison-based sorting algorithm can exist, therefore no such data structure can exist.

solved How to design a data structure which supports the following operations in constant time?