> - Require additional space bounded above by an exponential function in the input. > - May require an unbounded (though obviously finite) amount of time. How

> - Require additional space bounded above by an exponential function in the input. > - May require an unbounded (though obviously finite) amount of time. How can an algorithm that uses bounded space take unbounded time? Since the computation cannot be in the same memory state twice (otherwise it would loop), if it uses s bits of space it must complete in time O(2^s). In general, SPACE(f(n)) ⊆ DTIME(2^f(n)).