Prefix Sum Array in DSA Python - Time & Space Complexity

Time Complexity: Prefix Sum Array

O(n)

Understanding Time Complexity

We want to understand how fast we can build and use a prefix sum array.

How does the time needed grow as the input array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * n
    prefix[0] = arr[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + arr[i]
    return prefix

# Example usage:
# arr = [1, 2, 3, 4]
# prefix_sum(arr) returns [1, 3, 6, 10]

This code creates a new array where each element is the sum of all elements up to that position in the original array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single for-loop that adds elements one by one.
• How many times: The loop runs once for each element after the first, so (n - 1) times.

How Execution Grows With Input

As the input array gets bigger, the number of additions grows roughly the same as the size of the array.

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

Pattern observation: The operations increase linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the prefix sum array grows in direct proportion to the size of the input array.

Common Mistake

[X] Wrong: "Since we add numbers repeatedly, the time must be quadratic O(n²)."

[OK] Correct: Each addition uses the previous sum, so we only do one addition per element, not a sum over all previous elements each time.

Interview Connect

Knowing how prefix sums work and their time cost helps you solve many problems efficiently, like range sums or frequency counts.

Self-Check

"What if we wanted to build a 2D prefix sum array for a matrix? How would the time complexity change?"