Function calling - Time & Space Complexity

Time Complexity: Function calling

O(n)

Understanding Time Complexity

When we call a function in C, the program runs the code inside that function. We want to see how the time it takes changes when the function is called many times.

How does the number of function calls affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printNumbers(int n) {
    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
    }
}

int main() {
    printNumbers(5);
    printNumbers(5);
    return 0;
}
    

This code calls a function twice, and each call prints numbers from 0 up to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop inside the function that runs n times per call.
• How many times: The function is called twice, so the loop runs 2 x n times in total.

How Execution Grows With Input

Each function call runs a loop from 0 to n-1. Calling it twice means the total work doubles compared to calling it once.

Input Size (n)	Approx. Operations
10	20 (2 x 10)
100	200 (2 x 100)
1000	2000 (2 x 1000)

Pattern observation: The total work grows directly with n, just doubled because of two calls.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the input size n, even if the function is called multiple times a fixed number of times.

Common Mistake

[X] Wrong: "Calling the function twice makes the time complexity O(2n²) because it doubles and squares the work."

[OK] Correct: The function's loop runs n times per call, so two calls mean 2 x n operations, which is still linear, not squared. Constants like 2 do not change the overall growth type.

Interview Connect

Understanding how function calls add up helps you explain program speed clearly. It shows you can think about how repeated work affects performance, a useful skill in many coding situations.

Self-Check

"What if the function called itself recursively n times instead of being called twice? How would the time complexity change?"