I've been working with my student Marisa Kirisame on optimizing that space-time tradeoff, because different programs and different choices trade space for time at different efficiencies. Garbage collectors are an important way most programs trade space for time. So here I want to show a quick derivation that demonstrates how that optimization can occur. A Toy Model Consider a program that runs continuously with \(W\) bytes of live memory, and also generates garbage at a constant rate of \(g\)...
