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

Practice

1. What happens when a return statement is executed inside a loop in a C function?

easy

A. The program crashes due to an error.

B. The loop skips the current iteration and continues.

C. The loop finishes all iterations before returning.

D. The function immediately stops and returns the specified value.

Solution

1. Step 1: Understand the role of return inside a function

   The return statement immediately ends the function and sends back a value.

2. Step 2: Effect of return inside a loop

   When return is inside a loop, the function stops as soon as return is executed, even if the loop is not finished.

3. Final Answer:

   The function immediately stops and returns the specified value. -> Option D

4. Quick Check:

   Return inside loop = immediate function exit [OK]

Hint: Return inside loop stops function immediately [OK]

Common Mistakes:

• Thinking return only exits the loop, not the function
• Assuming loop completes before return
• Confusing return with continue or break

2. Which of the following is the correct syntax to return the value 5 inside a for loop in C?

easy

A. for(int i=0; i<3; i++) { return 5; }

B. for(int i=0; i<3; i++) return(5)

C. for(int i=0; i<3; i++) { return; 5; }

D. for(int i=0; i<3; i++) { return 5 }

Solution

1. Step 1: Check syntax of return statement

   Return must be followed by a value and a semicolon inside braces if used.

2. Step 2: Analyze each option

   for(int i=0; i<3; i++) { return 5; } uses correct syntax with braces and semicolon. for(int i=0; i<3; i++) return(5) misses semicolon, invalid. for(int i=0; i<3; i++) { return; 5; } has return without value then 5; which is invalid. for(int i=0; i<3; i++) { return 5 } misses semicolon after return 5.

3. Final Answer:

   for(int i=0; i<3; i++) { return 5; } -> Option A

4. Quick Check:

   Return syntax needs value and semicolon [OK]

Hint: Return must have value and semicolon inside braces [OK]

Common Mistakes:

• Omitting semicolon after return
• Placing code after return on same line
• Using return without value in non-void function

3. What is the output of this C function?

int findFirstEven(int arr[], int size) {
  for(int i = 0; i < size; i++) {
    if(arr[i] % 2 == 0) {
      return arr[i];
    }
  }
  return -1;
}

int main() {
  int nums[] = {3, 7, 8, 5};
  printf("%d", findFirstEven(nums, 4));
  return 0;
}

medium

A. 3

B. 7

C. 8

D. -1

Solution

1. Step 1: Trace the loop to find first even number

   The array is {3, 7, 8, 5}. Loop checks each element: 3 (odd), 7 (odd), 8 (even).

2. Step 2: Return when first even found

   At element 8, condition is true, so function returns 8 immediately, skipping rest.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Return stops loop at first even number 8 [OK]

Hint: Return inside loop returns first matching value [OK]

Common Mistakes:

• Assuming loop continues after return
• Returning wrong element index
• Confusing return value with loop index

4. Identify the error in this C function that tries to return the first negative number from an array:

int firstNegative(int arr[], int n) {
  for(int i=0; i

medium

A. The function has no return statement.

B. The function returns 0 too early, skipping rest of array.

C. The loop syntax is incorrect.

D. The function returns negative numbers incorrectly.

Solution

1. Step 1: Analyze the loop and return logic

   The else clause returns 0 immediately if the first element is not negative, so the loop never checks further elements.

2. Step 2: Understand why this is a problem

   This causes the function to stop early and miss negative numbers later in the array.

3. Final Answer:

   The function returns 0 too early, skipping rest of array. -> Option B

4. Quick Check:

   Return in else exits function too soon [OK]

Hint: Avoid return in else inside loop to check all elements [OK]

Common Mistakes:

• Returning inside else causes early exit
• Not using braces causing confusion
• Assuming loop checks all elements

5. You want to write a C function that returns the index of the first prime number in an array, or -1 if none found. Which code snippet correctly uses return inside a loop to achieve this?

hard

A. for(int i=0; i

B. for(int i=0; i

C. for(int i=0; i

D. for(int i=0; i

Solution

1. Step 1: Understand the goal

   We want to return the index of the first prime number found, or -1 if none.

2. Step 2: Analyze each option's logic

   for(int i=0; i

3. Final Answer:

   for(int i=0; i -> Option A

4. Quick Check:

   Return index on first prime, else -1 after loop [OK]

Hint: Return inside loop on condition, return default after loop [OK]

Common Mistakes:

• Returning wrong value inside loop
• Using break without return
• Returning default inside loop