The basic algorithmic issues discussed in Section 3.2 can be found in any text-book on data structure and algorithms. One can, for example, look at [7, 8, 61]. However, most of these elementary books do not talk about randomization and parallelization issues. We refer to  for a recent treatise on randomized algorithm. Also see Rabin’s papers [247, 248].
Complexity theory deals with classifying computational problems based on the known algorithms for solving them and on reduction of one problem to another. A simple introduction to complexity theory is the book  by Sipser. Chapter 2 of Koblitz’s book  is also a compact introduction to computational complexity meant for cryptographers. Also see [