filter() function in Python - Time & Space Complexity

Time Complexity: filter() function

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run the filter() function changes as the input list gets bigger.

Specifically, how does the number of items affect the work done inside filter()?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
filtered = list(filter(lambda x: x % 2 == 0, numbers))
print(filtered)

This code filters out even numbers from a list of numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The filter() function checks each item in the list one by one.
• How many times: It runs the check exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the number of checks grows in the same way.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of items. Double the items, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line with the size of the list.

Common Mistake

[X] Wrong: "The filter function only checks some items, so it runs faster than looking at every item."

[OK] Correct: The filter function must look at every item to decide if it passes the test or not, so it always checks all items.

Interview Connect

Understanding how filter() works helps you explain how your code handles data efficiently, a useful skill in many coding discussions.

Self-Check

"What if the filtering function itself took longer to run for each item? How would that affect the overall time complexity?"