np.cumsum() for cumulative sum in NumPy - Time & Space Complexity

Time Complexity: np.cumsum() for cumulative sum

O(n)

Understanding Time Complexity

We want to understand how the time taken by np.cumsum() changes as the input array grows.

Specifically, how does the work increase when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.array([1, 2, 3, 4, 5])
cum_sum = np.cumsum(arr)
print(cum_sum)

This code calculates the cumulative sum of the array elements, producing a new array where each element is the sum of all previous elements including itself.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each element to a running total to build the cumulative sum.
• How many times: Once for each element in the array, from start to end.

How Execution Grows With Input

As the array size grows, the number of additions grows in a straight line with it.

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

Pattern observation: The work grows evenly as the input size increases; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the cumulative sum grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Since cumulative sum involves sums of sums, it must take much longer than just adding all elements once."

[OK] Correct: The function cleverly adds each element only once in order, so it does not repeat sums unnecessarily.

Interview Connect

Understanding how simple array operations scale helps you explain and optimize data processing tasks clearly and confidently.

Self-Check

"What if we computed cumulative sums on a 2D array along one axis? How would the time complexity change?"