Time Complexity: Filter method
O(n)
0
0
Filter method in Javascript - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to run the filter method changes as the list gets bigger.
How does the work grow when we filter more items?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
const numbers = [1, 2, 3, 4, 5, 6];
const evenNumbers = numbers.filter(num => num % 2 === 0);
console.log(evenNumbers);
This code creates a new list with only the even numbers from the original list.
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 filter method checks more items 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 with the number of items.
Common Mistake
[X] Wrong: "Filter only looks at some items, so it runs faster than the list size."
[OK] Correct: Filter always checks every item to decide if it should keep it, so it takes time proportional to the whole list.
Interview Connect
Understanding how filter works helps you explain how your code handles data efficiently, a skill useful in many coding conversations.
Self-Check
"What if we used filter inside another loop over the same list? How would the time complexity change?"