Time Complexity: Select/filter for filtering
O(n)
0
0
Select/filter for filtering in Ruby - Time & Space Complexity
Understanding Time Complexity
When we use select or filter in Ruby, we want to pick certain items from a list based on a rule.
We ask: How does the time to do this grow as the list gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
filtered = numbers.select do |num|
num.even?
end
This code picks all even numbers from the list called numbers.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking each number to see if it is even.
- How many times: Once for every item in the list.
How Execution Grows With Input
As the list gets bigger, the program checks more numbers one by one.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The number of checks grows directly with the size of the list.
Final Time Complexity
Time Complexity: O(n)
This means the time to filter grows in a straight line as the list gets bigger.
Common Mistake
[X] Wrong: "Filtering only a few items means the program runs quickly no matter the list size."
[OK] Correct: The program still checks every item, even if only a few pass the filter.
Interview Connect
Understanding how filtering scales helps you explain how your code handles bigger data smoothly.
Self-Check
"What if we used a method that stops checking after finding the first match? How would the time complexity change?"