2 ms·
This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.
by delusional 1y ago
This is obviously demonstrably true. A Turing running in O(n) time must halt. The one in O(n) space is free not to.
- thaumasiotes 1y agoAlmondsetat's proof seems more obvious. Given O(n) time, you can only use O(n) space, so you're comparing "O(n) space, any amount of time" with "O(n) space, O(n) time", and it turns out you get more resources the first way.