Parameter passing mechanisms in Compiler Design - Time & Space Complexity

Time Complexity: Parameter passing mechanisms

O(n)

Understanding Time Complexity

When a program calls a function, it passes data to it using parameter passing mechanisms. Understanding how these mechanisms affect the time taken helps us see how function calls scale as input grows.

We want to know: how does the cost of passing parameters change when the size or number of parameters increases?

Scenario Under Consideration

Analyze the time complexity of passing parameters by value and by reference.

void func(int x, int &y) {
  x = x + 1;      // pass by value
  y = y + 1;      // pass by reference
}

int main() {
  int a = 5, b = 10;
  func(a, b);
}
    

This code shows a function receiving one parameter by value and one by reference, then modifying them.

Identify Repeating Operations

Look for operations that repeat or scale with input size.

• Primary operation: Copying the parameter passed by value.
• How many times: Once per parameter passed by value, for each function call.

How Execution Grows With Input

As the number or size of parameters passed by value grows, the copying work grows too.

Input Size (number or size of parameters)	Approx. Operations (copies)
10	10 copies
100	100 copies
1000	1000 copies

Pattern observation: The copying work grows directly with the number or size of parameters passed by value.

Final Time Complexity

Time Complexity: O(n)

This means the time to pass parameters grows linearly with the number or size of parameters passed by value.

Common Mistake

[X] Wrong: "Passing parameters by reference takes the same time as by value because both send data to the function."

[OK] Correct: Passing by reference only passes an address, which is a small fixed cost, while passing by value copies the entire data, which can be much larger and slower.

Interview Connect

Knowing how parameter passing affects time helps you explain function call costs clearly. This skill shows you understand how programs manage data efficiently.

Self-Check

"What if we changed all parameters to be passed by reference? How would the time complexity change?"

Practice

1. Which parameter passing mechanism sends a copy of the argument to the function, so changes inside the function do not affect the original variable?

easy

A. Pass by name

B. Pass by reference

C. Pass by value

D. Pass by result

Solution

1. Step 1: Understand pass by value

   Pass by value means the function receives a copy of the argument, so any changes inside the function do not affect the original variable.

2. Step 2: Compare with other mechanisms

   Pass by reference sends the original variable, so changes affect it. Pass by name and result behave differently and are less common.

3. Final Answer:

   Pass by value -> Option C

4. Quick Check:

   Copy sent, original unchanged = Pass by value [OK]

Hint: Copy means pass by value, original means pass by reference [OK]

Common Mistakes:

• Confusing pass by value with pass by reference
• Thinking pass by name sends a copy
• Assuming pass by result is the same as pass by value

2. Which of the following is the correct syntax to declare a function parameter passed by reference in C++?

easy

A. void func(int &x);

B. void func(int x);

C. void func(ref int x);

D. void func(*int x);

Solution

1. Step 1: Recall C++ reference syntax

   In C++, passing by reference uses the ampersand (&) symbol after the type in the parameter list.

2. Step 2: Analyze options

   void func(int &x); uses int &x which is correct. void func(int x); passes by value, C is invalid syntax, and D is pointer syntax, not reference.

3. Final Answer:

   void func(int &x); -> Option A

4. Quick Check:

   C++ reference uses & in parameter [OK]

Hint: Look for & symbol in parameter for C++ reference [OK]

Common Mistakes:

• Confusing pointer (*) with reference (&)
• Using invalid 'ref' keyword in C++
• Assuming no symbol means pass by reference

3. Consider the following pseudocode using pass by reference:

function increment(x) {
  x = x + 1
}

var a = 5
increment(a)
print(a)

What will be the output?

medium

A. 5

B. Undefined

C. Error

D. 6

Solution

1. Step 1: Understand pass by reference effect

   Since x is passed by reference, the function changes the original variable a by adding 1.

2. Step 2: Trace the code execution

   a starts at 5, increment adds 1 making it 6, then print outputs 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Pass by reference changes original = 6 [OK]

Hint: Pass by reference changes original variable [OK]

Common Mistakes:

• Assuming pass by reference behaves like pass by value
• Thinking the original variable remains unchanged
• Ignoring the effect of increment inside the function

4. Identify the error in this code snippet using pass by value:

function swap(x, y) {
  temp = x
  x = y
  y = temp
}

var a = 3
var b = 4
swap(a, b)
print(a, b)

medium

A. Print statement is incorrect

B. swap function does not swap original variables

C. Variables a and b are not declared

D. Syntax error in function definition

Solution

1. Step 1: Understand pass by value behavior in swap

   Since parameters are passed by value, swap changes only local copies x and y, not original a and b.

2. Step 2: Check the output effect

   After swap call, a and b remain 3 and 4, so swap does not work as intended.

3. Final Answer:

   swap function does not swap original variables -> Option B

4. Quick Check:

   Pass by value means original unchanged [OK]

Hint: Pass by value swaps local copies only [OK]

Common Mistakes:

• Assuming swap changes original variables with pass by value
• Looking for syntax errors where none exist
• Ignoring parameter passing mechanism effect

5. You want to write a function that modifies a list of numbers by doubling each element. Which parameter passing mechanism is best to use to ensure the original list is changed efficiently?

hard

A. Pass by reference

B. Pass by value

C. Pass by name

D. Pass by result

Solution

1. Step 1: Consider efficiency and effect on original list

   Pass by value copies the entire list, which is inefficient and changes won't affect original.

2. Step 2: Choose mechanism that modifies original efficiently

   Pass by reference sends the original list, allowing direct modification without copying.

3. Final Answer:

   Pass by reference -> Option A

4. Quick Check:

   Modify original efficiently = Pass by reference [OK]

Hint: Modify original data efficiently with pass by reference [OK]

Common Mistakes:

• Choosing pass by value and expecting original change
• Confusing pass by name with pass by reference
• Ignoring efficiency of copying large data