of the algorithm. Finally, the break table relocation records are used to adjust pointer fields inside the relocated objects. The live objects are examined for pointers, which can be looked up in the sorted break table of size n in O(log n) time if the break table is sorted, for a total running time of O(n log n). Pointers are then adjusted by the amount specified in the relocation table. LISP 2 algorithm In order to avoid O(n log n) complexity, the algorithm uses three different passes over the heap. In addition, heap objects must have a separate forwarding pointer slot that is not used outside of garbage collection. After standard marking, the algorithm proceeds in the following three passes: Compute the forwarding location for live objects. Keep track of a free and live pointer and initialize both to the start of heap. If the live pointer points to a live object, update that object's forwarding pointer to the current free pointer and increment the free pointer according to the object's size. Move the live pointer to the next object End when the live pointer reaches the end of heap. Update all pointers For each live object, update its pointers according to the forwarding pointers of the objects they point to. Move objects For each live object, move its data to its forwarding location. This algorithm is O(n) on the size of the heap; it has a better complexity than the table-based approach, but the table-based approach's n is the size of the used space only, not the entire heap space as in the LISP2 algorithm. However, the LISP2 algorithm is simpler to implement. See also Dead-code elimination References Automatic memory management Memory management algorithms