For Algorithms, Memory Is a Far More Powerful Resource Than Time

That classic result was a way to transform any algorithm with a given time budget into a new algorithm with a slightly smaller space budget. Williams saw that a simulation based on squishy pebbles would make the new algorithm’s space usage much…