List comprehension with condition in Python - Time & Space Complexity

Time Complexity: List comprehension with condition

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a list comprehension with a condition changes as the input list grows.

Specifically, how does filtering items while creating a new list affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Create a list of even numbers only
even_numbers = [num for num in numbers if num % 2 == 0]

This code creates a new list containing only the even numbers from the original list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each number in the list to see if it is even.
• How many times: Once for every item in the input 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 complete the list comprehension grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Because we only keep some items, the time taken is less than checking all items."

[OK] Correct: The program still looks at every item to decide if it fits the condition, so it must check all items no matter what.

Interview Connect

Understanding how filtering with list comprehensions scales helps you explain efficiency clearly in interviews and shows you know how loops and conditions affect performance.

Self-Check

"What if we replaced the list comprehension with a filter function? How would the time complexity change?"