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?"

Practice

1. What does the following list comprehension do?
[x for x in range(5) if x % 2 == 0]

easy

A. Creates a list of odd numbers from 0 to 4

B. Creates a list of even numbers from 0 to 4

C. Creates a list of numbers from 1 to 5

D. Creates a list of numbers divisible by 3

Solution

1. Step 1: Understand the range and condition

   The range(5) generates numbers 0, 1, 2, 3, 4. The condition x % 2 == 0 selects numbers divisible by 2 (even numbers).

2. Step 2: Apply the condition to each number

   From 0 to 4, the even numbers are 0, 2, and 4. These are included in the new list.

3. Final Answer:

   [0, 2, 4] -> Option B

4. Quick Check:

   Even numbers from 0 to 4 = [0, 2, 4] [OK]

Hint: Look for the condition after 'if' to filter items [OK]

Common Mistakes:

• Confusing even and odd numbers
• Ignoring the condition and taking all numbers
• Misunderstanding the range function

2. Which of the following is the correct syntax for a list comprehension that selects numbers greater than 10 from list nums?

easy

A. [x for x > 10 in nums]

B. [x if x > 10 for x in nums]

C. [if x > 10 for x in nums]

D. [x for x in nums if x > 10]

Solution

1. Step 1: Recall list comprehension syntax

   The correct syntax is [expression for item in iterable if condition]. Here, expression and item are both x, iterable is nums, and condition is x > 10.

2. Step 2: Check each option

   [x for x in nums if x > 10] matches the correct syntax. The other options have misplaced or missing parts.

3. Final Answer:

   [x for x in nums if x > 10] -> Option D

4. Quick Check:

   Correct list comprehension syntax = [x for x in nums if x > 10] [OK]

Hint: Remember: for comes before if in list comprehension [OK]

Common Mistakes:

• Placing 'if' before 'for'
• Omitting 'for' keyword
• Using incorrect order of clauses

3. What is the output of this code?

nums = [3, 7, 12, 5, 20]
result = [n*2 for n in nums if n > 6]
print(result)

medium

A. [14, 24, 40]

B. [3, 7, 12, 5, 20]

C. [6, 14, 24, 10, 40]

D. [12, 24, 40]

Solution

1. Step 1: Identify numbers greater than 6

   From the list, numbers greater than 6 are 7, 12, and 20.

2. Step 2: Multiply each selected number by 2

   7*2=14, 12*2=24, 20*2=40. These form the new list.

3. Final Answer:

   [14, 24, 40] -> Option A

4. Quick Check:

   Filter >6 and double = [14, 24, 40] [OK]

Hint: Apply condition first, then transform each item [OK]

Common Mistakes:

• Multiplying all numbers, ignoring condition
• Including numbers less than or equal to 6
• Confusing multiplication with addition

4. Find the error in this list comprehension:

values = [1, 2, 3, 4]
new_values = [x for x in values if x > 2 else 0]

medium

A. SyntaxError due to incorrect use of else in list comprehension

B. No error, code runs fine

C. TypeError because of wrong condition

D. NameError because x is undefined

Solution

1. Step 1: Understand list comprehension with condition

   In list comprehension, 'if' can be used to filter items, but 'else' must be part of a conditional expression, not after 'if' alone.

2. Step 2: Identify the syntax error

   The code uses 'if x > 2 else 0' incorrectly. The correct way is to use a conditional expression inside the expression part, like [x if x > 2 else 0 for x in values].

3. Final Answer:

   SyntaxError due to incorrect use of else in list comprehension -> Option A

4. Quick Check:

   Else must be inside expression, not after if clause [OK]

Hint: Use if-else inside expression, not after if clause [OK]

Common Mistakes:

• Placing else after if in list comprehension filter
• Confusing filter condition with conditional expression
• Ignoring Python syntax rules for comprehensions

5. You have a list of strings: words = ['apple', '', 'banana', 'cherry', '', 'date']. Which list comprehension creates a new list with only non-empty strings in uppercase?

hard

A. [w for w in words if w.upper()]

B. [w.upper() if w else w for w in words]

C. [w.upper() for w in words if w]

D. [w.upper() for w in words if w == '']

Solution

1. Step 1: Understand filtering non-empty strings

   In Python, empty strings are false in boolean context. Using if w filters out empty strings.

2. Step 2: Convert filtered strings to uppercase

   For each non-empty string w, w.upper() converts it to uppercase.

3. Final Answer:

   [w.upper() for w in words if w] -> Option C

4. Quick Check:

   Filter non-empty and uppercase = [w.upper() for w in words if w] [OK]

Hint: Use 'if w' to filter non-empty strings in list comprehension [OK]

Common Mistakes:

• Filtering empty strings incorrectly
• Using if-else incorrectly inside comprehension
• Not converting strings to uppercase