Less memory traffic can matter as much as fewer operations
Asymptotic bounds abstract away cache lines, allocation, and locality. Two O(n) algorithms can behave differently when one scans contiguous primitive storage and another follows scattered object references.
fun prefixTotals(values: IntArray): LongArray {
val sums = LongArray(values.size + 1)
for (i in values.indices) sums[i + 1] = sums[i] + values[i]
return sums
}
The sequential scan creates a predictable access pattern. Prefix totals use extra O(n) storage but answer later range-sum queries in O(1), excluding validation. For dynamic updates, this precomputed structure becomes stale and another structure may be appropriate.
Blocking matrix computations into tiles can improve locality, but tile size depends on data layout and hardware. Avoid hard-coded performance claims without measurements on the target workload.
Exercise
Benchmark sequential versus deliberately scattered access over the same values. Measure allocation separately and keep the arithmetic identical. Then compare a full DP table with rolling rows where dependencies permit it.
Check: space compression must preserve required predecessor values; updating in the wrong order can produce fast but incorrect results.