Prefix Sum Array in DSA C - 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.

void buildPrefixSum(int arr[], int prefix[], int n) {
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
}

int rangeSum(int prefix[], int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];
}
    

This code builds a prefix sum array from an input array and then uses it to find the sum of elements between two indexes quickly.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 1 to n-1 to build the prefix sums.
• How many times: It runs exactly n-1 times, once for each element after the first.

How Execution Grows With Input

As the input array size grows, the number of steps to build the prefix sum grows roughly the same amount.

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

Pattern observation: The work grows linearly with input size; doubling the input roughly doubles the work.

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: "Calculating the sum of any range using the prefix sum array takes O(n) time because we still add elements."

[OK] Correct: Using the prefix sum array, range sums are found with just two lookups and one subtraction, which is O(1) time, not O(n).

Interview Connect

Understanding prefix sums helps you quickly answer range sum queries, a common pattern in coding problems. Mastering this shows you can optimize repeated calculations efficiently.

Self-Check

"What if we needed to update elements in the array frequently? How would that affect the time complexity of using a prefix sum array?"