Time Complexity: Scalar and array broadcasting
O(n)
0
0
Scalar and array broadcasting in NumPy - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to run numpy operations changes when using scalars with arrays.
Specifically, how does adding a single number to a big array affect the work done?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
import numpy as np
arr = np.arange(1000)
scalar = 5
result = arr + scalar
This code adds a single number to every element in a numpy array using broadcasting.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Adding the scalar to each element of the array.
- How many times: Once for each element in the array (1000 times here).
How Execution Grows With Input
As the array size grows, the number of additions grows the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 additions |
| 100 | 100 additions |
| 1000 | 1000 additions |
Pattern observation: The work grows directly with the number of elements.
Final Time Complexity
Time Complexity: O(n)
This means the time to add a scalar to an array grows linearly with the array size.
Common Mistake
[X] Wrong: "Adding a scalar to an array is instant and does not depend on array size."
[OK] Correct: Even though numpy uses fast operations, it still needs to add the scalar to each element, so time grows with array size.
Interview Connect
Understanding how broadcasting affects performance helps you explain efficient numpy code clearly in interviews.
Self-Check
"What if we added two arrays of the same size instead of a scalar and an array? How would the time complexity change?"