TAOCP 2.3.5 Exercise 6
The term $c_2 M$ arises from the tracing phase of the garbage collection procedure, in which all nodes that are reachable from the list heads are marked by following their structural links.
Section 2.3.5: Lists and Garbage Collection
Exercise 6. [**] [00] The quantitative discussion at the end of this section says that the cost of garbage collection is approximately $c_1N+c_2M$ units of time; where does the "$c_2M$" term come from?
Verified: yes
Solve time: 43s
The term $c_2 M$ arises from the tracing phase of the garbage collection procedure, in which all nodes that are reachable from the list heads are marked by following their structural links. Let $M$ denote the number of nodes that are actually reachable and therefore visited during this traversal.
During this phase, each reachable node is examined and its pointer fields are followed to discover further nodes, so each such node contributes a constant amount of work for inspection and propagation of marks. The total cost of this traversal is therefore proportional to the number of reachable nodes, yielding a term of the form $c_2 M$, where $c_2$ is the constant cost per visited node in the marking process.
The remaining term $c_1 N$ accounts for the initial sweep through all $N$ memory locations to test and initialize marks, while $c_2 M$ comes from the subsequent graph traversal restricted to the $M$ nodes that are actually live. This completes the explanation. ∎