Garbage collection basics in Compiler Design - Time & Space Complexity

Time Complexity: Garbage collection basics

O(n)

Understanding Time Complexity

We want to understand how the time cost of garbage collection changes as the program's memory usage grows.

How does the work of cleaning unused memory scale with more objects?

Scenario Under Consideration

Analyze the time complexity of the following garbage collection process.

// Simple mark-and-sweep garbage collector
function garbageCollect(heap) {
  for (const object of heap) {
    object.marked = false;
  }
  markRoots();
  for (const object of heap) {
    if (!object.marked) {
      free(object);
    }
  }
}

function markRoots() {
  for (const root of roots) {
    mark(root);
  }
}

function mark(object) {
  if (object.marked) return;
  object.marked = true;
  for (const child of object.references) {
    mark(child);
  }
}
    

This code marks all reachable objects starting from roots, then frees unmarked objects.

Identify Repeating Operations

Look for loops and recursion that repeat work.

• Primary operation: Traversing all objects and their references to mark reachable ones.
• How many times: Each object is visited once during marking; then all objects are checked once during sweeping.

How Execution Grows With Input

As the number of objects (n) grows, the collector must check and mark more objects.

Input Size (n)	Approx. Operations
10	About 20 (mark + sweep)
100	About 200
1000	About 2000

Pattern observation: The work grows roughly in direct proportion to the number of objects.

Final Time Complexity

Time Complexity: O(n)

This means the time to collect garbage grows linearly with the number of objects in memory.

Common Mistake

[X] Wrong: "Garbage collection time stays the same no matter how many objects exist."

[OK] Correct: The collector must visit each object to check if it is still used, so more objects mean more work.

Interview Connect

Understanding how garbage collection time grows helps you explain performance impacts in real programs and shows you can reason about resource management.

Self-Check

"What if the garbage collector used a generational approach that only checks new objects? How would the time complexity change?"