Function calling in C++ - Time & Space Complexity

Time Complexity: Function calling

O(n)

Understanding Time Complexity

When we call a function in a program, it takes some time to run. Understanding how this time grows helps us write faster code.

We want to know: how does the time to run change when we call a function many times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int square(int x) {
    return x * x;
}

int main() {
    int sum = 0;
    int n = 100;
    for (int i = 1; i <= n; i++) {
        sum += square(i);
    }
    return 0;
}
    

This code calls a function square inside a loop to calculate the sum of squares from 1 to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop runs from 1 to n.
• How many times: The square function is called once each loop, so n times total.

How Execution Grows With Input

As n grows, the number of times we call the function grows the same way.

Input Size (n)	Approx. Operations
10	10 calls to square
100	100 calls to square
1000	1000 calls to square

Pattern observation: The total work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of times we call the function.

Common Mistake

[X] Wrong: "Calling a simple function inside a loop adds no extra time."

[OK] Correct: Even a simple function call takes time, and calling it n times adds up, so it affects total time.

Interview Connect

Knowing how function calls add up helps you explain code speed clearly and shows you understand how programs work step by step.

Self-Check

"What if the function square called another function inside it? How would the time complexity change?"