Loop optimization (invariant code motion) in Compiler Design - Time & Space Complexity

Time Complexity: Loop optimization (invariant code motion)

O(n)

Understanding Time Complexity

When a program runs a loop, some calculations inside might not need to be repeated every time. Moving these out can save time.

We want to see how this change affects the total work done as the loop grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    int x = a + b;  // invariant calculation
    arr[i] = x * i;
}
    

This loop calculates the same sum a + b every time, then uses it to update an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs n times.
• How many times: The addition a + b is done inside the loop, repeating n times.

How Execution Grows With Input

Each time the loop runs, it does the addition and a multiplication.

Input Size (n)	Approx. Operations
10	About 20 operations (10 additions + 10 multiplications)
100	About 200 operations
1000	About 2000 operations

Pattern observation: The total work grows directly with n. Doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the loop grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "Doing the same calculation inside the loop doesn't affect performance much."

[OK] Correct: Even small repeated work adds up when the loop runs many times, making the program slower.

Interview Connect

Understanding how moving repeated work outside loops saves time shows you can write efficient code, a skill valued in many programming tasks.

Self-Check

"What if the calculation inside the loop depends on the loop variable? How would that affect the time complexity?"