Return values in C++ - Time & Space Complexity

Time Complexity: Return values

O(n)

Understanding Time Complexity

Let's see how the time it takes to run code with return values changes as the input grows.

We want to know how the program's steps increase when returning values from a function.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}
    

This function adds up all numbers in an array and returns the total sum.

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: It runs once for each element in the array, so n times.

How Execution Grows With Input

As the array gets bigger, the number of additions grows too.

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

Pattern observation: The work grows directly with the size of the input array.

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: "Returning a value makes the function run instantly, no matter the input size."

[OK] Correct: The return itself is quick, but the work done before returning depends on input size, so time grows with input.

Interview Connect

Understanding how return values relate to time helps you explain function efficiency clearly and confidently.

Self-Check

"What if the function returned the sum of only the first half of the array? How would the time complexity change?"