Nested list comprehension in Python - Time & Space Complexity

Time Complexity: Nested list comprehension

O(n * m)

Understanding Time Complexity

When we use nested list comprehensions, the computer repeats some steps many times.

We want to know how the time needed grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

matrix = [[1, 2], [3, 4], [5, 6]]
result = [y * 2 for x in matrix for y in x]

This code multiplies each number inside each inner list by 2 and collects the results in one list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop goes through each element inside each inner list.
• How many times: For each inner list, it runs once for every element inside it.

How Execution Grows With Input

Imagine the matrix has n inner lists, each with m elements.

Input Size (n x m)	Approx. Operations
10 x 2	20
100 x 5	500
1000 x 10	10,000

Pattern observation: The total steps grow by multiplying the number of inner lists by the number of elements inside each.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows in proportion to the total number of elements inside all inner lists combined.

Common Mistake

[X] Wrong: "Nested list comprehensions always mean the time is squared, like O(n²)."

[OK] Correct: The time depends on how many elements are inside each inner list. If inner lists are small or fixed size, the time grows mostly with the outer list size.

Interview Connect

Understanding how nested loops inside list comprehensions affect time helps you explain your code clearly and shows you can think about efficiency.

Self-Check

"What if the inner lists have different lengths? How would the time complexity change?"