<p>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.</p>

<p>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":</p>

<p>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).</p>

<p>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 <em>a priori</em> knowledge of the use case informs the best approach).</p>

<p>This implies there is some inherent "total work" required to solve $X$, <em>regardless of choice of</em> $Y$, and paints the picture that for all solutions $Y$ to problem $X$, $Mem(Y)*Time(Y)\geq TotWork(X)$:
<a href="https://i.sstatic.net/WeZLj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WeZLj.png" alt="enter image description here"></a>
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.</p>

<p>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...)</p>

CC BY-SA 3.0
2017-05-27T12:20:32.573Z
The keyword to search for in the literature is “space-time tradeoff”.
Emil Jeřábek
CC BY-SA 3.0
2017-05-27T22:43:15.390Z
Usually known as "time-space tradeoff" (spacetime is something else).
Yuval Filmus
CC BY-SA 3.0
2017-05-28T10:43:26.047Z
sometimes known as "time-memory" tradeoff.
kodlu
CC BY-SA 3.0
2017-05-28T20:34:57.233Z
Circuit complexity is a nice measure of "total work" needed to compute a (class of) function(s)
daniello
<cc.complexity-theory><ds.algorithms><reference-request><soft-question>
Notion of "total work" of a problem?
charlestoncrabb
# Notion of "total work" of a problem?

(Asked by: username_0 on 2017-05-27)

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](https://i.sstatic.net/WeZLj.png)](https://i.sstatic.net/WeZLj.png)
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...)

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, soft-question
> **Comments:**
> **username_1**: The keyword to search for in the literature is “space-time tradeoff”.  
> **username_2**: Usually known as "time-space tradeoff" (spacetime is something else).  
> **username_3**: sometimes known as "time-memory" tradeoff.  
> **username_4**: Circuit complexity is a nice measure of "total work" needed to compute a (class of) function(s)  

---

## 0 answers

