Basic list comprehension syntax in Python - Time & Space Complexity

Time Complexity: Basic list comprehension syntax

O(n)

Understanding Time Complexity

We want to understand how the time needed to create a new list using list comprehension changes as the input list grows.

How does the number of steps grow when we use list comprehension on bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5]
squares = [x * x for x in numbers]

This code creates a new list of squares from the original list of numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each number by itself inside the list comprehension.
• How many times: Once for each item in the input list.

How Execution Grows With Input

As the input list gets bigger, the number of multiplications grows at the same rate.

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

Pattern observation: The work grows directly with the size of the input list.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the new list grows in a straight line with the input size.

Common Mistake

[X] Wrong: "List comprehension is faster because it does everything at once, so time doesn't grow with input size."

[OK] Correct: Even though list comprehension looks simple, it still processes each item one by one, so time grows with the number of items.

Interview Connect

Understanding how list comprehension scales helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we added a condition inside the list comprehension to filter items? How would the time complexity change?"

Practice

1. What does the following list comprehension do?
[x * 2 for x in range(3)]

easy

A. Creates a list of numbers from 1 to 6

B. Creates a list of numbers from 0 to 3

C. Creates a list of numbers doubled from 0 to 2

D. Creates a list of numbers squared from 0 to 2

Solution

1. Step 1: Understand the range and loop variable

   The range(3) generates numbers 0, 1, 2. The variable x takes these values one by one.

2. Step 2: Apply the expression to each value

   Each x is multiplied by 2, so the list becomes [0*2, 1*2, 2*2] = [0, 2, 4].

3. Final Answer:

   Creates a list of numbers doubled from 0 to 2 -> Option C

4. Quick Check:

   List comprehension doubles each number in range(3) [OK]

Hint: Remember: for x in range(3) gives 0,1,2 only [OK]

Common Mistakes:

• Thinking range(3) includes 3
• Confusing doubling with squaring
• Ignoring the for loop variable

2. Which of the following is the correct syntax for a list comprehension that creates a list of squares of numbers 0 to 4?

easy

A. [x**2 x in range(5)]

B. [for x in range(5) x**2]

C. [x^2 in range(5)]

D. [x**2 for x in range(5)]

Solution

1. Step 1: Recall list comprehension syntax

   The correct syntax is [expression for variable in iterable]. Here, expression is x**2 and iterable is range(5).

2. Step 2: Check each option

   [x**2 for x in range(5)] matches the correct syntax. Options A, B, and C have syntax errors or wrong order.

3. Final Answer:

   [x**2 for x in range(5)] -> Option D

4. Quick Check:

   Correct syntax is [expr for var in iterable] [OK]

Hint: Remember: list comprehension = [expression for variable in iterable] [OK]

Common Mistakes:

• Placing 'for' after expression
• Using ^ instead of ** for power
• Missing 'in' keyword

3. What is the output of this code?

nums = [1, 2, 3, 4]
squares = [n*n for n in nums if n % 2 == 0]
print(squares)

medium

A. [4, 16]

B. [1, 4, 9, 16]

C. [2, 4]

D. [1, 9]

Solution

1. Step 1: Understand the list and condition

   The list nums is [1, 2, 3, 4]. The condition 'if n % 2 == 0' selects even numbers: 2 and 4.

2. Step 2: Calculate squares of selected numbers

   Squares of 2 and 4 are 4 and 16, so the list squares is [4, 16].

3. Final Answer:

   [4, 16] -> Option A

4. Quick Check:

   Filter even numbers, then square them [OK]

Hint: Filter first, then apply expression in list comprehension [OK]

Common Mistakes:

• Including odd numbers by mistake
• Confusing values with their squares
• Ignoring the if condition

4. Find the error in this list comprehension:

result = [x + 1 for in range(5)]

medium

A. Missing variable name after 'for'

B. Using + instead of *

C. range(5) should be range(1,5)

D. List comprehension cannot use range

Solution

1. Step 1: Check the for loop syntax inside comprehension

   The syntax requires a variable name after 'for', like 'for x in range(5)'. Here, 'x' is missing.

2. Step 2: Identify the error

   Because the variable is missing, Python will raise a syntax error.

3. Final Answer:

   Missing variable name after 'for' -> Option A

4. Quick Check:

   for loop needs variable name [OK]

Hint: Always include variable after 'for' in comprehension [OK]

Common Mistakes:

• Omitting the loop variable
• Misplacing 'in' keyword
• Thinking range needs to start at 1

5. You have a list of words: words = ['apple', 'bee', 'cat', 'dog', 'elephant']. Using list comprehension, how do you create a list of the lengths of words that have more than 3 letters?

hard

A. [w for w in words if len(w) > 3]

B. [len(w) for w in words if len(w) > 3]

C. [len(words) for w in words if len(w) > 3]

D. [len(w) > 3 for w in words]

Solution

1. Step 1: Understand the filtering condition

   We want only words with length greater than 3, so use 'if len(w) > 3' to filter.

2. Step 2: Create list of lengths

   For each filtered word, get its length with len(w). So the comprehension is [len(w) for w in words if len(w) > 3].

3. Final Answer:

   [len(w) for w in words if len(w) > 3] -> Option B

4. Quick Check:

   Filter words by length, then get lengths [OK]

Hint: Filter first, then apply len() in comprehension [OK]

Common Mistakes:

• Returning words instead of lengths
• Using len(words) instead of len(w)
• Returning boolean instead of lengths