# Finding lower bounds for data structures with non-standard interfaces

Consider the problem of designing a data structure that provides the interface functions $\rm{pop}, \rm{push}, \rm{findmin}$, all running in constant time. This problem may be solved by (e.g.) having the $\rm{push}$ method compute the new minimum as well, and place it on the stack together with the pushed element.

Is there any systematic approach to determining lower bounds (of time and space complexity) for data structures exposing a given set of interfaces? E.g. $\rm{push,pop,sort, insertAtIndex}$? Can you provide links to relevant literature?

• This is an entire subarea of theoretical computer science. You can take a look at Patrascu's thesis, for example. Dec 30 '17 at 9:55
• @YuvalFilmus Can you make that an answer?
– PKG
Dec 30 '17 at 22:29