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

Practice

1. What does it mean to call a function in C?

easy

A. Execute the code inside the function by using its name and parentheses

B. Define the function with its code block

C. Declare the function prototype

D. Write comments about the function

Solution

1. Step 1: Understand function calling

   Calling a function means running the code inside it by using its name followed by parentheses.

2. Step 2: Differentiate from defining or declaring

   Defining or declaring a function is writing it, not running it. Calling is executing it.

3. Final Answer:

   Execute the code inside the function by using its name and parentheses -> Option A

4. Quick Check:

   Function call = run code by name() [OK]

Hint: Calling means running code by writing functionName() [OK]

Common Mistakes:

• Confusing calling with defining the function
• Thinking calling means declaring the function prototype
• Believing calling is writing comments

2. Which of the following is the correct syntax to call a function named printMessage in C?

easy

A. printMessage();

B. call printMessage;

C. printMessage;

D. function printMessage();

Solution

1. Step 1: Recall function call syntax

   In C, calling a function requires its name followed by parentheses and a semicolon.

2. Step 2: Check each option

   printMessage(); uses correct syntax: function name + parentheses + semicolon. Others are invalid syntax.

3. Final Answer:

   printMessage(); -> Option A

4. Quick Check:

   Function call syntax = name() [OK]

Hint: Function call always ends with (); [OK]

Common Mistakes:

• Omitting parentheses when calling
• Using keywords like 'call' which don't exist in C
• Missing semicolon at the end

3. What will be the output of this C program?

void greet() {
    printf("Hello!\n");
}

int main() {
    greet();
    return 0;
}

medium

A. Compilation error

B. Hello!

C. No output

D. greet()

Solution

1. Step 1: Understand function greet()

   The function greet() prints "Hello!" followed by a newline.

2. Step 2: Check main() function call

   Main calls greet(), so the program prints "Hello!" on the screen.

3. Final Answer:

   Hello! -> Option B

4. Quick Check:

   Calling greet() prints Hello! [OK]

Hint: Calling greet() prints its message exactly [OK]

Common Mistakes:

• Thinking function name prints output
• Assuming no output without explicit main print
• Confusing function call with declaration

4. Identify the error in this code snippet:

void sayHi() {
    printf("Hi!\n");
}

int main() {
    sayHi;
    return 0;
}

medium

A. printf statement is incorrect

B. Missing semicolon after sayHi

C. Function sayHi is not declared

D. Missing parentheses when calling sayHi

Solution

1. Step 1: Check function call syntax

   In main(), sayHi is written without parentheses, so it is not a function call.

2. Step 2: Correct function call

   To call sayHi, it must be written as sayHi(); with parentheses.

3. Final Answer:

   Missing parentheses when calling sayHi -> Option D

4. Quick Check:

   Function call needs () [OK]

Hint: Always use () to call a function [OK]

Common Mistakes:

• Omitting parentheses when calling functions
• Confusing function name with variable
• Assuming semicolon alone calls function

5. Given the function below, how would you call multiply to multiply 4 and 5 and print the result?

int multiply(int a, int b) {
    return a * b;
}

int main() {
    // Your code here
    return 0;
}

hard

A. int result = multiply(4, 5);

B. multiply(4, 5);

C. printf("%d", multiply(4, 5));

D. print(multiply(4, 5));

Solution

1. Step 1: Understand multiply function

   It returns the product of two integers.

2. Step 2: Call multiply and print result

   To show output, call multiply(4, 5) inside printf with %d format.

3. Final Answer:

   printf("%d", multiply(4, 5)); -> Option C

4. Quick Check:

   Use printf to display function return [OK]

Hint: Use printf to show returned value from function [OK]

Common Mistakes:

• Calling multiply without printing result
• Using print() instead of printf() in C
• Assigning result but not printing