Any?, all?, none? predicates in Ruby - Time & Space Complexity

Time Complexity: Any?, all?, none? predicates

O(n)

Understanding Time Complexity

When using predicates like any?, all?, and none? in Ruby, it's important to understand how the time to run them changes as the list gets bigger.

We want to know how many steps the program takes when checking these conditions on a list.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

result = numbers.any? do |num|
  num > 5
end

puts result

This code checks if any number in the list is greater than 5.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterating over the list elements one by one.
• How many times: Up to the entire list length, but may stop early if condition is met.

How Execution Grows With Input

As the list gets bigger, the number of checks grows, but sometimes it stops early.

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 checks can stop early if the condition is met, so the time can be less than the list size, but in the worst case it checks every item.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows linearly with the list size in the worst case.

Common Mistake

[X] Wrong: "These predicates always check every item in the list no matter what."

[OK] Correct: Actually, any?, all?, and none? stop checking as soon as they know the answer, so they often do less work than the full list length.

Interview Connect

Understanding how these predicates work helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if we changed any? to all?? How would the time complexity change when the condition is rarely true?"