Time-Space Trade-offs

Spending memory to save time

Many speed-ups work by using more memory. Hash sets and maps turn repeated O(n) searches into O(1) average lookups at the cost of O(n) space. Memoisation stores results of subproblems so they are computed once, turning exponential recursion into polynomial time. Precomputation builds structures once to answer many queries quickly: a prefix-sum array answers any range-sum query in O(1) after O(n) preprocessing, instead of O(n) per query; sorting once enables binary searches. Lookup tables replace computation with memory reads. The trade-off can go the other way when memory is tight: recomputing values, streaming data instead of loading it, or using in-place algorithms. The right choice depends on constraints: how many queries, how large the data, how much RAM. In interviews, presenting both options ("O(n²) time and O(1) space, or O(n) time and O(n) space with a hash set") shows mature thinking.

Prefix sums: O(n) preprocessing, O(1) per query

Answering q range-sum queries drops from O(n·q) to O(n + q).

def build_prefix(a):
    prefix = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        prefix[i + 1] = prefix[i] + x      # O(n) time, O(n) space
    return prefix

def range_sum(prefix, left, right):        # inclusive left..right
    return prefix[right + 1] - prefix[left]  # O(1) per query

sales = [120, 80, 150, 90, 200, 60]
p = build_prefix(sales)
range_sum(p, 1, 3)                         # 80 + 150 + 90

# without prefix sums: sum(sales[l:r+1]) per query is O(n) each

Name the trade-off explicitly

Say which resource you are spending and why it is affordable, for example "extra O(n) memory is fine for one million integers, about 8 MB in a packed array".

त्वरित जाँच: Prefix sums answer each range-sum query in O(1). What do they cost?

• Nothing
• O(n²) space
• O(n) preprocessing time and O(n) extra space
• O(log n) per query