Return inside loops in C - Time & Space Complexity

Time Complexity: Return inside loops

O(n)

Understanding Time Complexity

When a return statement is inside a loop, it can stop the loop early. This affects how long the code runs.

We want to know how the running time changes as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int findFirstPositive(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            return arr[i];
        }
    }
    return -1;
}
    

This code looks for the first positive number in an array and returns it immediately when found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array elements one by one.
• How many times: Up to n times, but can stop earlier if a positive number is found.

How Execution Grows With Input

Execution depends on where the first positive number appears.

Input Size (n)	Approx. Operations
10	Between 1 and 10 checks
100	Between 1 and 100 checks
1000	Between 1 and 1000 checks

Pattern observation: The loop may stop early, so the time can be less than n, but in the worst case it checks all elements.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the size of the input in the worst case.

Common Mistake

[X] Wrong: "Because the return stops the loop early, the time is always constant."

[OK] Correct: Sometimes the positive number is near the start, but if it is at the end or missing, the loop runs through all elements.

Interview Connect

Understanding how early returns affect loops helps you explain code efficiency clearly and shows you think about best and worst cases.

Self-Check

"What if the return statement was replaced with a variable assignment and the loop always ran to the end? How would the time complexity change?"