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?"

Practice

1. What is a reference in C++?

easy

A. A pointer to a variable

B. A new variable with its own memory

C. An alias for another variable

D. A constant value

Solution

1. Step 1: Understand the definition of a reference

   A reference acts as another name for an existing variable, not a separate variable.

2. Step 2: Compare with other options

   Unlike pointers or constants, references directly alias the original variable.

3. Final Answer:

   An alias for another variable -> Option C

4. Quick Check:

   Reference = Alias [OK]

Hint: Remember: reference is just another name for a variable [OK]

Common Mistakes:

• Confusing references with pointers
• Thinking references create new memory
• Believing references can be reassigned

2. Which of the following is the correct syntax to declare a reference to an int variable x?

easy

A. int &ref = x;

B. int ref& = x;

C. int &ref(x);

D. int ref = &x;

Solution

1. Step 1: Recall correct reference syntax

   References are declared with the & symbol after the type: int &ref = x;.

2. Step 2: Check other options for syntax errors

   int ref& = x; places & incorrectly, C uses parentheses which is invalid here, D uses pointer syntax.

3. Final Answer:

   int &ref = x; -> Option A

4. Quick Check:

   Reference syntax = type &name = variable [OK]

Hint: Put & right after type, before variable name [OK]

Common Mistakes:

• Placing & after variable name
• Using parentheses instead of = for initialization
• Confusing references with pointers (& usage)

3. What is the output of this code?

int a = 5;
int &ref = a;
ref = 10;
std::cout << a << std::endl;

medium

A. 5

B. Undefined behavior

C. Compilation error

D. 10

Solution

1. Step 1: Understand reference assignment

   Reference ref aliases a, so assigning to ref changes a.

2. Step 2: Trace the output

   After ref = 10;, a becomes 10, so printing a outputs 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Reference assignment changes original variable [OK]

Hint: Changing reference changes original variable [OK]

Common Mistakes:

• Thinking ref is separate variable
• Expecting original variable unchanged
• Confusing reference with pointer syntax

4. Identify the error in this code:

int x = 5;
int &ref;
ref = x;

medium

A. Cannot assign int to reference

B. Reference must be initialized when declared

C. Variable x is not declared

D. No error, code is correct

Solution

1. Step 1: Check reference declaration rules

   References must be initialized at declaration; int &ref; without initialization is invalid.

2. Step 2: Analyze the code

   Here, ref is declared without initialization, causing a compilation error.

3. Final Answer:

   Reference must be initialized when declared -> Option B

4. Quick Check:

   References need initialization [OK]

Hint: Always initialize references when declaring [OK]

Common Mistakes:

• Declaring references without initialization
• Confusing assignment after declaration with initialization
• Ignoring compiler errors on references

5. Given the code below, what will be the output?

int a = 3;
int b = 4;
int &ref = a;
ref = b;
std::cout << a << ", " << b << std::endl;

What does this demonstrate about references?

hard

A. Reference assignment changes the original variable's value

B. Reference creates a copy of the variable

C. Reference can be reassigned to another variable

D. Reference points to the address of another variable

Solution

1. Step 1: Understand reference initialization

   ref is a reference to a, fixed at initialization.

2. Step 2: Analyze ref = b;

   This assigns the value of b to a through ref, not reassigning the reference.

3. Step 3: Determine output

   After assignment, a becomes 4, b remains 4, so output is 4, 4.

4. Final Answer:

   Reference assignment changes the original variable's value -> Option A

5. Quick Check:

   Reference fixed; assignment changes value [OK]

Hint: Reference fixed at init; assignment changes value, not reference [OK]

Common Mistakes:

• Thinking reference can be reassigned to another variable
• Confusing reference with pointer behavior
• Assuming reference copies value