1
$\begingroup$

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?

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

Data structure lower bounds is a full-fledged area in theory of computation. The main model of computation on which the lower bounds are proved is the cell probe model, which counts the number of memory accesses, but for which computation is free. For an overview of how things stood in 2008, you can take a look at Mihai Pătraşcu's thesis. Tragically, Pătraşcu died from brain cancer in 2012 at the age of 29.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.