Reference lifetime in C++ - Time & Space Complexity

Time Complexity: Reference lifetime

O(n)

Understanding Time Complexity

When working with references in C++, it's important to understand how long they last during program execution.

We want to see how the program's steps grow as the input size changes when references are involved.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int& findMax(int arr[], int n) {
    int& maxRef = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] > maxRef) {
            maxRef = arr[i];
        }
    }
    return maxRef;
}
    

This function finds the maximum value in an array and returns a reference to it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that checks each element once.
• How many times: The loop runs exactly n-1 times, where n is the array size.

How Execution Grows With Input

As the array size grows, the number of steps grows in a straight line with it.

Input Size (n)	Approx. Operations
10	9
100	99
1000	999

Pattern observation: The work increases evenly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the max grows directly with the number of elements.

Common Mistake

[X] Wrong: "Returning a reference makes the function faster and changes the time complexity."

[OK] Correct: Returning a reference only avoids copying but does not reduce the number of steps to find the max.

Interview Connect

Understanding how reference lifetime and loops affect time helps you explain code efficiency clearly and confidently.

Self-Check

"What if we changed the function to return a copy of the max value instead of a reference? How would the time complexity change?"