Passing parameters by reference in C++ - Time & Space Complexity

Time Complexity: Passing parameters by reference

O(n)

Understanding Time Complexity

When we pass parameters by reference in C++, it can affect how fast our program runs, especially with large data.

We want to see how this choice changes the number of steps the program takes as input grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void increment(int &x) {
    x = x + 1;
}

int main() {
    int n = 1000;
    int total = 0;
    for (int i = 0; i < n; i++) {
        increment(total);
    }
    return 0;
}
    

This code increases a number by 1, repeating it n times using a function that takes the number by reference.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop calls the increment function n times.
• How many times: Exactly n times, where n is the input size.

How Execution Grows With Input

Each time we increase n, the number of steps grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 increments
100	About 100 increments
1000	About 1000 increments

Pattern observation: The work grows evenly as n grows; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Passing by reference makes the function run faster by reducing the number of operations inside the loop."

[OK] Correct: Passing by reference avoids copying data but does not reduce how many times the loop runs or how many increments happen.

Interview Connect

Understanding how passing by reference affects time helps you write efficient code and explain your choices clearly in real projects.

Self-Check

"What if the increment function took the parameter by value instead of by reference? How would the time complexity change?"