Actually, even without cycles the destruction time is in general unbounded. Just think what happens when you allocate a very long linked list one element at a time and then drop the head. With a bit of ill luck or intention, you can make each element be allocated from a different page with enough different pages so that they fall out of the TLB. In that situation, even without having pages written out to disk, you can expect each element to take ~ a thousand cycles to free. On a million element list, that's ~500ms for freeing the head.