3
$\begingroup$

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction.

I am curious if there is a theoretical notion of "total work" of a problem, and possibly what kind of analyses could be done to explore the work required of a given problem. I realize this question is quite "soft", but any insight would sate my curiosity. Let me explain what I mean by "total work":

Suppose we have problem $X$ (e.g., sort a set of objects by some key, solve an initial/boundary value PDE, find all $4-$cycles in a graph, etc...), and we come up with some algorithm $Y$. We can do some asymptotic analysis to come up with some performance bounds, (e.g., $O(\log n)$ time but $\Omega(n^2)$ memory).

Now, algorithm $Y$ was just one of perhaps an infinite number of ways to solve problem $X$, making the performance of $Y$ a property of $Y$ rather than $X$. In my (limited) experience, there seems to almost always be a theme of "different $Y$'s for different guys": $Y_1$ will provide optimal time of an algorithm at the expense of memory, whereas $Y_2$ will solve $X$ with the absolute least amount of memory while forfeiting the time speed-up logic; a prototypical example being using adjacency lists vs adjacency matrices for graph representations (though in this example a priori knowledge of the use case informs the best approach).

This implies there is some inherent "total work" required to solve $X$, regardless of choice of $Y$, and paints the picture that for all solutions $Y$ to problem $X$, $Mem(Y)*Time(Y)\geq TotWork(X)$: enter image description here This is of course a gross simplification, as there are any number of things that contribute to the overall performance of an algorithm, whether it's machine architecture, parallelizability, language, etc., but it seems in all cases there is a set number of resources required to solve a problem, and the algorithm can be chosen to suit the respective availability of resources.

Is there any literature on this concept? (As I'm writing this, I'm thinking the concept is so fundamental to algorithm design and analysis that it's probably in any freshman text...)

$\endgroup$
  • 5
    $\begingroup$ The keyword to search for in the literature is “space-time tradeoff”. $\endgroup$ – Emil Jeřábek supports Monica May 27 '17 at 12:20
  • 1
    $\begingroup$ Usually known as "time-space tradeoff" (spacetime is something else). $\endgroup$ – Yuval Filmus May 27 '17 at 22:43
  • $\begingroup$ sometimes known as "time-memory" tradeoff. $\endgroup$ – kodlu May 28 '17 at 10:43
  • 1
    $\begingroup$ Circuit complexity is a nice measure of "total work" needed to compute a (class of) function(s) $\endgroup$ – daniello May 28 '17 at 20:34

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.