Reference declaration in C++ - Time & Space Complexity

Time Complexity: Reference declaration

O(n)

Understanding Time Complexity

Let's see how declaring references affects the time it takes for a program to run.

We want to know if using references changes how the program's work grows as input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int arr[], int n) {
    int &total = *new int(0); // reference to an int
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    int result = total;
    delete &total; // free memory
    return result;
}
    

This code sums all elements of an array using a reference to an integer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that adds each array element to total.
• How many times: Exactly n times, once for each element in the array.

How Execution Grows With Input

As the array size grows, the loop runs more times, adding each element once.

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

Pattern observation: The work grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using a reference makes the loop run faster or slower."

[OK] Correct: The reference itself does not add extra loops or slow down the repeated work; it just points to the same memory, so the main work is still the loop over the array.

Interview Connect

Understanding how references affect time helps you explain your code clearly and shows you know what really costs time in programs.

Self-Check

"What if we replaced the reference with a normal integer variable inside the loop? How would the time complexity change?"