Common subexpression elimination in Compiler Design - Time & Space Complexity

Time Complexity: Common subexpression elimination

O(n²)

Understanding Time Complexity

When a compiler removes repeated calculations, it saves time. We want to know how the time to optimize grows as the program size grows.

How does the work of finding repeated expressions change when the code gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for each basic block in program:
  for each expression in block:
    if expression seen before in block:
      replace with previous result
    else:
      record expression

This code finds repeated expressions inside each block and replaces duplicates with stored results.

Identify Repeating Operations

Look for loops or repeated checks that take most time.

• Primary operation: Checking each expression against previously seen ones in the same block.
• How many times: For each expression in each block, this check happens once per previously seen expression.

How Execution Grows With Input

As the number of expressions grows, the number of checks grows too.

Input Size (n expressions)	Approx. Operations
10	About 55 checks
100	About 5,050 checks
1000	About 500,500 checks

Pattern observation: The number of checks grows roughly like the square of the number of expressions.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of expressions, the work to find repeats roughly quadruples.

Common Mistake

[X] Wrong: "Finding repeated expressions only takes time proportional to the number of expressions."

[OK] Correct: Because each new expression is compared to all previous ones, the total checks add up much faster than just counting expressions.

Interview Connect

Understanding how optimization steps grow with program size helps you explain compiler efficiency clearly. It shows you can think about how tools work behind the scenes.

Self-Check

"What if we used a fast lookup structure like a hash table to track expressions? How would the time complexity change?"