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