Time Complexity: Basic list comprehension syntax
O(n)
0
0
Basic list comprehension syntax in Python - Time & Space Complexity
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?"