Function declaration and definition - Time & Space Complexity

Time Complexity: Function declaration and definition

O(n)

Understanding Time Complexity

When we write functions in C, it's important to know how their running time changes as inputs grow.

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 sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}
    

This function adds up all elements 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 visits each element of the array once.
• How many times: Exactly n times, where n is the size of the array.

How Execution Grows With Input

As the array size grows, 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; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the function grows in a straight line with the input size.

Common Mistake

[X] Wrong: "The function runs in constant time because it just sums values."

[OK] Correct: Even though the operation is simple, it must visit every element, so time grows with n.

Interview Connect

Understanding how function time grows helps you explain your code clearly and shows you know how to write efficient programs.

Self-Check

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

Practice

1. What is the purpose of a function declaration in C?

easy

A. To allocate memory for variables inside the function

B. To execute the function's code

C. To tell the compiler about the function's name, return type, and parameters before its use

D. To print the function's output

Solution

1. Step 1: Understand function declaration role

   A function declaration informs the compiler about the function's name, return type, and parameters so it can be used before its definition.

2. Step 2: Differentiate declaration from definition

   Declaration does not contain the function's code; that is done in the definition.

3. Final Answer:

   To tell the compiler about the function's name, return type, and parameters before its use -> Option C

4. Quick Check:

   Function declaration = Inform compiler [OK]

Hint: Declaration tells compiler about function before use [OK]

Common Mistakes:

• Confusing declaration with definition
• Thinking declaration runs the function
• Assuming declaration allocates memory

2. Which of the following is a correct function declaration in C?

easy

A. int add { int a, int b; };

B. int add(int a, int b) {}

C. add(int a, int b) int;

D. int add(int a, int b);

Solution

1. Step 1: Identify correct syntax for declaration

   A function declaration includes the return type, function name, parameter list, and ends with a semicolon.

2. Step 2: Check each option

   int add(int a, int b); matches correct syntax: return type 'int', name 'add', parameters '(int a, int b)', and semicolon. Others have syntax errors or missing semicolon.

3. Final Answer:

   int add(int a, int b); -> Option D

4. Quick Check:

   Declaration ends with semicolon [OK]

Hint: Declaration ends with semicolon and no body [OK]

Common Mistakes:

• Missing semicolon at end
• Including function body in declaration
• Wrong parameter syntax

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

#include <stdio.h>

int multiply(int x, int y);

int main() {
    printf("%d", multiply(3, 4));
    return 0;
}

int multiply(int x, int y) {
    return x * y;
}

medium

A. 12

B. 7

C. 34

D. Compilation error

Solution

1. Step 1: Understand function declaration and call

   The function 'multiply' is declared before main and defined after. main calls multiply(3, 4).

2. Step 2: Calculate function return value

   multiply returns 3 * 4 = 12, which is printed by printf.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   3 * 4 = 12 [OK]

Hint: Declaration allows call before definition [OK]

Common Mistakes:

• Thinking declaration runs code
• Confusing output with parameters
• Expecting compilation error due to declaration

4. Identify the error in this function declaration and definition:

int sum(int a, int b)
{
    return a + b
}

medium

A. Function name is invalid

B. Missing semicolon after return statement

C. Parameters must be declared outside parentheses

D. Return type should be void

Solution

1. Step 1: Check syntax inside function body

   The return statement must end with a semicolon in C.

2. Step 2: Identify missing semicolon

   Here, 'return a + b' lacks a semicolon, causing a syntax error.

3. Final Answer:

   Missing semicolon after return statement -> Option B

4. Quick Check:

   Statements end with semicolon [OK]

Hint: Return statements need semicolon [OK]

Common Mistakes:

• Omitting semicolon after return
• Misunderstanding parameter syntax
• Changing return type unnecessarily

5. You want to declare and define a function that calculates the average of three integers and returns a float. Which of the following is the correct declaration and definition?

hard

A. float average(int a, int b, int c);

float average(int a, int b, int c) {
return (a + b + c) / 3.0;
}

B. int average(int a, int b, int c);

int average(int a, int b, int c) {
return (a + b + c) / 3.0;
}

C. float average(int a, int b, int c);

float average(int a, int b, int c) {
return (a + b + c) / 3;
}

D. float average(int a, int b, int c) {
return (a + b + c) / 3;
}

Solution

1. Step 1: Check function declaration matches definition

   Declaration and definition must have same return type (float) and parameters (three ints).

2. Step 2: Ensure correct calculation for float average

   To get float result, divide by 3.0 (float), not 3 (int).

3. Step 3: Verify other options

   Integer division (/ 3) causes truncation. Declaring int return but dividing by 3.0 causes type mismatch. Missing declaration prevents prior use.

4. Final Answer:

   float average(int a, int b, int c); float average(int a, int b, int c) { return (a + b + c) / 3.0; } -> Option A

5. Quick Check:

   Float division needs 3.0 [OK]

Hint: Use float division (3.0) and matching declaration [OK]

Common Mistakes:

• Using integer division instead of float
• Mismatching declaration and definition types
• Omitting function declaration