Function declaration and definition in C++ - Time & Space Complexity

Time Complexity: Function declaration and definition

O(n)

Understanding Time Complexity

When we write functions, it's important to know how their running time changes as the input grows.

We want to see how the work inside a function scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Function declaration
int sumArray(int arr[], int n);

// Function definition
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 of size n and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that adds each element to total.
• How many times: It runs once for each element, so n times.

How Execution Grows With Input

As the array gets bigger, the function does more additions, one per element.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	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: "The function runs in constant time because it just adds numbers."

[OK] Correct: The function must add each number one by one, so more numbers mean more work.

Interview Connect

Understanding how function work time grows helps you explain your code clearly and shows you think about efficiency.

Self-Check

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