In the preceding chapters when analyzing an algorithm involving dynamically allocated storage, we assume that the time taken to acquire or to release storage is bounded by a constant. Specifically, Axiom in Chapter states that the running time of operator new is a constant, , and that the running time of operator delete is also a constant, .
But is this really so? To answer this question, we consider in this chapter the dynamic management of a pool of memory. In particular, we consider several different implementations for the operators new and delete and we show that the assumptions of constant running times are not always valid.