Find/detect for first match in Ruby - Time & Space Complexity

Time Complexity: Find/detect for first match

O(n)

Understanding Time Complexity

When we look for the first item that matches a condition, we want to know how long it takes as the list grows.

We ask: How does the time to find the first match change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 3, 5, 8, 10]
result = numbers.find { |num| num.even? }
puts result

This code looks through the list to find the first even number and stops once it finds it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each number one by one to see if it is even.
• How many times: Up to the first even number found, or the whole list if none found.

How Execution Grows With Input

As the list gets bigger, the time depends on where the first match is.

Input Size (n)	Approx. Operations
10	Checks 1 to 10 items depending on first match
100	Checks 1 to 100 items depending on first match
1000	Checks 1 to 1000 items depending on first match

Pattern observation: The time grows with the position of the first match, up to the full list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the first match grows linearly with the list size in the worst case.

Common Mistake

[X] Wrong: "Finding the first match always takes the same time no matter the list size."

[OK] Correct: If the match is near the start, it's fast, but if it's near the end or missing, it takes longer as the list grows.

Interview Connect

Understanding how searching stops early helps you explain efficient code and shows you know how loops behave with different inputs.

Self-Check

"What if we changed find to select to get all matches? How would the time complexity change?"