0.08.1.8.7.18 prologs before heap allocated blocks that point to an information structure about the block so that finding the information on a block is O(1) instead of O(n) for n number of allocated blocks as when traversing the whole table. However, malloc() and free() still are O(n) because of traversing free lists.