Prefix Sum Complexity Analysis: When O(n) Space is Worth It

Interviewer: "Your solution uses O(n) extra space. Can you do better?"

You: "Well... prefix sum needs O(n) space for the prefix array..."

Interviewer: "Is that necessary?"

You need to justify the tradeoff.

TL;DR

Prefix sum tradeoff:

• Time: O(n) preprocessing + O(1) per query
• Space: O(n)

Worth it when:

• Multiple queries (q ≥ 2)
• Query time matters
• Space is available

Not worth it when:

• Single query only
• Space is critical
• Can use O(1) space alternative

Time Complexity Breakdown

Preprocessing: O(n)

prefix = [0]
for num in nums:  # O(n)
    prefix.append(prefix[-1] + num)

Query: O(1)

sum_range = prefix[j+1] - prefix[i]  # O(1)

Total for q queries: O(n + q)

Space Complexity

O(n) for prefix array

Can't be reduced if you want O(1) queries.

Tradeoff Analysis

Problem: Answer q range sum queries on array of size n.

Break-even point: When q ≥ 2, prefix sum is already faster.

Example: Multiple Queries

n = 10,000
q = 1,000 queries

Brute force: 10,000 × 1,000 = 10,000,000 operations
Prefix sum: 10,000 + 1,000 = 11,000 operations

Speedup: ~900× faster!
Space cost: 10,000 integers (~40KB)

Worth it? Absolutely!

When O(n) Space is Worth It

✅ Worth It When:

1. Multiple queries (q ≥ 2)
2. Query time critical (need O(1))
3. Space available (not constrained)
4. Static array (no updates)

❌ Not Worth It When:

1. Single query only
2. Space critical (embedded systems)
3. Can use O(1) alternative (Kadane's for max subarray)

Interview Justification

Interviewer: "Why use O(n) space?"

You: "With q queries, brute force is O(q × n). Prefix sum is O(n + q), which is ~q times faster when q is large. The O(n) space cost is justified by the massive time savings."

Interviewer: "What if space is limited?"

You: "If we must use O(1) space and have multiple queries, we'd accept O(q × n) time. For a single query, we don't need prefix sum at all—just calculate the sum directly in O(n)."

Alternative: Segment Tree

When updates are needed:

• Segment Tree: O(log n) update, O(log n) query, O(n) space
• Prefix sum: O(n) rebuild per update

Tradeoff: Segment tree is better for dynamic arrays.

Conclusion

Key takeaways:

• Prefix sum: O(n) space for O(1) queries
• Worth it when q ≥ 2
• Justify with time savings

The formula:

• Brute force: O(q × n)
• Prefix sum: O(n + q)
• Speedup: ~q times

For more, see the complete guide and 1D template.