2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.