Time Complexity: List comprehension with if-else
O(n)
0
0
List comprehension with if–else in Python - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time needed to run a list comprehension with if-else changes as the input list grows.
Specifically, how does adding a condition inside the comprehension affect the work done?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
numbers = [1, 2, 3, 4, 5]
result = [x * 2 if x % 2 == 0 else x + 1 for x in numbers]This code creates a new list by doubling even numbers and adding one to odd numbers from the original list.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: One loop over the input list, checking each number and applying a simple calculation.
- How many times: Exactly once for each item in the list.
How Execution Grows With Input
As the list gets bigger, the program does more checks and calculations, one for each item.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks and calculations |
| 100 | 100 checks and calculations |
| 1000 | 1000 checks and calculations |
Pattern observation: The work grows directly with the number of items; doubling the list doubles the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to finish grows in a straight line with the size of the input list.
Common Mistake
[X] Wrong: "Adding an if-else inside the list comprehension makes it slower than a simple loop without conditions."
[OK] Correct: The if-else check happens once per item, just like any operation in a loop, so it does not add extra loops or nested work. The overall time still grows linearly.
Interview Connect
Understanding how conditions inside list comprehensions affect time helps you write clear and efficient code, a skill valued in real projects and interviews.
Self-Check
"What if we replaced the if-else with two separate list comprehensions, one filtering evens and one filtering odds, then combined the results? How would the time complexity change?"