When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A datacenter only has so many ram seconds in a day.

The spacetime complexity of most algorithms, i.e. their cost in ram-seconds, is just their time cost multiplied by their space cost. But suppose an algorithm had an $\Theta(n)$ time startup phase that required $\Theta(n)$ space to compute a couple required details, followed by an $\Theta(n^2)$ time serial computation that only needed $\Theta(\log^2 n)$ space. This algorithm's spacetime complexity would be $\Theta(n^2 \log^2 n)$ instead of the $O(n^3)$ you'd get by multiplying its time complexity by its space complexity.

Are any real life, practical examples of algorithms with spacetime complexity lower than their time complexity times their space complexity?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.