Time Complexity: Predicate methods (ending with ?)
O(n)
0
0
Predicate methods (ending with ?) in Ruby - Time & Space Complexity
Understanding Time Complexity
We want to understand how long it takes for predicate methods to run as the input changes.
Specifically, we ask: how does the time grow when checking conditions with these methods?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
def all_even?(numbers)
numbers.all? { |num| num.even? }
end
list = [2, 4, 6, 8, 10]
puts all_even?(list)This code checks if all numbers in a list are even using a predicate method.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Iterating over each number in the list to check if it is even.
- How many times: Up to once per element, stopping early if a number is not even.
How Execution Grows With Input
As the list gets longer, the method checks more numbers, but it may stop early if a number is odd.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 10 checks |
| 100 | Up to 100 checks |
| 1000 | Up to 1000 checks |
Pattern observation: The number of checks grows roughly in direct proportion to the list size.
Final Time Complexity
Time Complexity: O(n)
This means the time to check grows linearly with the number of items in the list.
Common Mistake
[X] Wrong: "Predicate methods always run in constant time because they just check a condition."
[OK] Correct: Even though the check is simple, the method may need to look at every item in the list, so time grows with input size.
Interview Connect
Understanding how predicate methods scale helps you explain your code's efficiency clearly and confidently.
Self-Check
"What if we changed all? to any?? How would the time complexity change?"