logoalt Hacker News

jasperryyesterday at 8:42 PM0 repliesview on HN

Sure, there are plenty of computations where you don't need much space no matter how many times you loop--like if you're just updating a single sum. But there are other problems where each time through the loop you might need to add an element to a big array or matrix, and then you go back and do more computation on the saved data elements to get the answer.

Before this result, there were believed to be at least some problems where you need (almost) as much space as time, but Williams shows that, theoretically at least, that's never necessarily the case.