Return inside loops in Java - Time & Space Complexity

Time Complexity: Return inside loops

O(n)

Understanding Time Complexity

We want to see how quickly this code runs when it uses a return inside a loop.

How does stopping early affect the work done as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public boolean containsValue(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) {
            return true;
        }
    }
    return false;
}
    

This code checks if a target number is inside an array and stops as soon as it finds it.

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 the length of the array, but may stop early if target found.

How Execution Grows With Input

When the target is near the start, the loop stops quickly. When it is not found, the loop checks every item.

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 work can be small if the target is found early, or grow linearly if not found.

Final Time Complexity

Time Complexity: O(n)

This means the time grows roughly in direct proportion to the size of the input array in the worst case.

Common Mistake

[X] Wrong: "Because there is a return inside the loop, the code always runs fast and does not depend on input size."

[OK] Correct: The return only stops the loop early if the target is found quickly. If not found, the loop still checks every element, so time depends on input size.

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 we removed the return and instead used a flag variable to check after the loop? How would the time complexity change?"