<p>Most computations in algebraic geometry / commutative algebra.</p>
<p>Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes.  I think one of the first papers to look at this was Bayer &amp; Mumford &quot;<a href="https://arxiv.org/abs/alg-geom/9304003" rel="noreferrer">What can be computed in algebraic geometry?</a>&quot;.</p>
<p>(FWIW, my recent experience with these programs has been that there is a trichotomy: either the answer returns in (1) seconds, (2) a few minutes, or (3) so long that you give up / so much memory that it crashes.)</p>

CC BY-SA 4.0
2020-08-13T19:56:48.847Z
2020-08-13T19:56:48.847Z
Joshua Grochow
<p>Dynamic programming is probably a general case of this but one specific, practically relevant and illustrative example is (global) <a href="https://en.wikipedia.org/wiki/Sequence_alignment#Pairwise_alignment" rel="noreferrer">pairwise sequence alignment</a> using the <a href="https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm" rel="noreferrer">Needleman–Wunsch algorithm</a>, which has both time and space complexity <span class="math-container">$\mathcal O(nm)$</span>.</p>
<p>When applied to mammalian whole-genome alignments, this would naïvely require in the order of exabytes of space. Even bacterial genome alignments still require terabytes. By contrast, there’s a <a href="https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm" rel="noreferrer">clever variation of the algorithm due to Hirshberg</a> that uses divide &amp; conquer to require only linear space (<span class="math-container">$\mathcal O(\min\{n,m\})$</span>). This algorithm is also faster in practice (because it reduces the search space) but even if it didn’t improve the runtime it would still be practically feasible, whereas Needleman and Wunsch’s algorithm has prohibitive space requirements for all but small sequences.</p>

CC BY-SA 4.0
2020-08-15T13:25:08.900Z
2020-08-15T13:25:08.900Z
Konrad Rudolph
<p>My go-to answer for this (the one I use in undergraduate algorithms classes) is the Bellman–Held–Karp dynamic programming algorithm for the traveling salesperson problem (<a href="https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm" rel="noreferrer">https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm</a>). It's not the choice in practice for this problem (instead, branch-and-cut methods like in CONCORDE are faster) but it has the best proven time guarantees for the general problem, and its <span class="math-container">$O(n^2 2^n)$</span> time and <span class="math-container">$O(n2^n)$</span> space are in the range to make the space bound the bottleneck. There are alternative algorithms using polynomial space but with a higher exponential time bound, roughly <span class="math-container">$4^n$</span>.</p>

CC BY-SA 4.0
2020-08-13T19:14:16.653Z
2020-08-13T19:14:16.653Z
David Eppstein
<p>In knowledge compilation, the task is to compile some set <span class="math-container">$A\subseteq \{0,1\}^n$</span> into a format such that various queries can then be answered in polynomial time. For example, you can &quot;compile&quot; the set of satisfying assignments to a CNF formula <span class="math-container">$\psi$</span> into a Binary Decision Diagram (a kind of directed acyclic labelled graph). Once this is (expensive) computation is done, one can then do many things cheaply that are usually expensive.</p>
<p>For example, one can count the satisfying assignments of a CNF formula in time linear in the size of this BDD graph. If you have compiled two CNFs <span class="math-container">$\phi,\psi$</span> into BDDs, then you can check whether <span class="math-container">$\phi\implies \psi$</span>, and count <span class="math-container">$|\phi\wedge \psi|$</span>, in time <span class="math-container">$\Theta(|\phi|_{\text{BDD}}\cdot |\psi|_{\text{BDD}})$</span>. This is significant, because a BDD can be exponentially smaller than the set that it encodes: some formulas have an exponential number of satisfying assignments, but have a BDD of size only, say, <span class="math-container">$\mathcal{O}(n^2)$</span>.
The BDD of any clause <span class="math-container">$(x_1\vee x_2\vee\cdots\vee x_{k})$</span> has size only <span class="math-container">$\Theta(k)$</span>, so after building the BDD of a formula <span class="math-container">$\phi$</span> BDD <em><strong>once</strong></em>, one can then check for clausal entailment <span class="math-container">$\phi\implies (x_1\vee x_2\vee\cdots\vee x_k)$</span>, for any clause, very quickly, in time <span class="math-container">$\Theta(|\psi|_{\text{BDD}}\cdot k)$</span>. Normally these computations are <span class="math-container">$\#\text{P}$</span>-Complete and <span class="math-container">$\text{NP}$</span>-Complete, respectively.</p>
<p>In an ideal situation, we have the opportunity to build the BDD during &quot;preprocessing time&quot;, and once we're done, we hear which query we are supposed to answer. Then the limiting factor is that the BDD may grow exponentially in size. This blowup was always unavoidable, of course: We are trying to do intractable computations in polynomial time, so the tradeoff that we make is that the representation is exponentially large. Fortunately, in practice, this exponential behaviour rarely happens, and many interesting functions and systems can be represented by surprisingly small BDDs. For example, formulas with small treewidth have small BDDs.</p>
<p>Another wonderful application: the set <span class="math-container">$A$</span> is be the set of reachable configurations of a piece of software, or the reachable positions in chess. This is how BDDs made their debut: One can do exhaustive search on the state space of a program by compiling it into a BDD, and then one checks, for example, whether that set contains an element in which the program counters of two threads are in the same critical section. This last predicate is a simple formula with a small BDD, so intersection checking is fast.</p>
<p>Since the introduction of BDDs in 1986 [1], a large zoo of new diagrams have sprung up for this purpose: ZDDs, Tagged BDDs, SDDs, d-DNNFs. They make time/space tradeoffs: They are more compact, but support less queries. A good (but slightly out-of-date) overview is <em>A knowledge compilation map</em> [2]. All these diagrams are ultimately Boolean circuits, so finding out which ones are more compact than others is a difficult question of circuit lower bounds, so is part of computational complexity theory.</p>
<p>Of course BDDs are not always the answer, and modern model checking seems to favour SAT-based approaches, but Bryant's paper has 12k citations, so it is safe to say that people have found some uses for them.</p>
<p>[1] Bryant, Randal E. &quot;Graph-based algorithms for boolean function manipulation.&quot; Computers, IEEE Transactions on 100.8 (1986): 677-691.</p>
<p>[2] Darwiche, Adnan, and Pierre Marquis. &quot;A knowledge compilation map.&quot; Journal of Artificial Intelligence Research 17 (2002): 229-264.</p>

CC BY-SA 4.0
2020-08-13T20:28:58.267Z
2020-08-13T20:28:58.267Z
Lieuwe Vinkhuijzen
<p>One example is multicommodity flow problems via Simplex method. In these problems we have a graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$n$</span> nodes and <span class="math-container">$m$</span> edges and <span class="math-container">$K$</span> commodities. The number of variables is <span class="math-container">$Km$</span> (one per commodity and edge pair) and the number of constraints is roughly <span class="math-container">$m$</span>. Now if you try to run the flow problem via simplex based algorithms then the incidence matrix is too large and inverting it creates a dense matrix which does not often fit in memory even though the initial problem is of reasonable size. This is one reason people use column generation and approximate iterative methods.</p>

CC BY-SA 4.0
2020-08-13T20:47:40.077Z
I would think that the issue of memory would also be relevant to interior point methods.
Chandra Chekuri
CC BY-SA 4.0
2020-08-13T20:00:28.430Z
2020-08-13T20:00:28.430Z
Chandra Chekuri
<p>I don't know if the space complexity of this problem is <em>limiting</em> in practice (I have not personally run experiments to verify this, moreover I don't know anyone who needs to solve exact SVP in practice --- approximating it to some polynomial approx factor is already sufficient to break cryptography), but algorithms solving the Shortest Vector Problem in <span class="math-container">$n$</span>-dimensional integer lattices fall into a few different classes:</p>
<ol>
<li><a href="http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Enum.html" rel="noreferrer">Enumeration</a> methods: <span class="math-container">$O(n^n)$</span> time, poly space</li>
<li><a href="http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Sieve.html" rel="noreferrer">Sieving</a> methods: exponential time, exponential space, and randomized</li>
<li><a href="http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Voronoi.html" rel="noreferrer">Voronoi Cell Computations</a>: exponential time, exponential space</li>
</ol>
<p>This is to say all known exact SVP algorithms with provable running time <span class="math-container">$2^{O(n)}$</span> use exponential space, and algorithms with polynomial space usage have running time <span class="math-container">$2^{\omega(n)}$</span>.</p>

CC BY-SA 4.0
2020-08-13T19:29:58.177Z
2020-08-13T19:29:58.177Z
Mark Schultz-Wu
<p>With this question we actually have to worry about <a href="https://en.wikipedia.org/wiki/Analysis_of_algorithms#Constant_factors" rel="nofollow noreferrer"><span class="math-container">$O(1)$</span> factors</a>, because as you point out time can't be little o of space, but it can be much less demanding as a fraction of our hardware's abilities. A historical example, in which many algorithms could be discussed to make the point, would be old-school video games. I won't go into much detail here, but will lean on links; for now, it suffices to say it's mostly been about reducing the redundancy in data, sometimes <a href="https://retrocomputing.stackexchange.com/questions/11476/how-did-satoru-iwata-compress-pokemon-gs-to-fit-two-regions-on-a-single-cartridg">caring literally about every single bit</a>.</p>
<p>Nowadays, you can afford to give every pixel independent 24-bit colour in every frame. But <a href="https://www.youtube.com/watch?v=Tfh0ytz8S0k" rel="nofollow noreferrer">there was a time</a> you couldn't even achieve 2-bit colour that way, due to limited RAM. The reason that's no longer true is because RAM has grown much more in the last 40 years or so than screen resolution has. There were similar issues <a href="https://www.youtube.com/watch?v=q_3d1x2VPxk" rel="nofollow noreferrer">with audio</a>.</p>
<p>The same period has also seen hardware expand how large the whole game can be, which may not sound like an algorithm detail, but it is because (1) game developers used to have to do all sorts of inventive things to do all they could with memory (here's a <a href="https://www.youtube.com/watch?v=ZWQ0591PAxM" rel="nofollow noreferrer">modern take</a> on just a few of them) and (2) modern games' large size is typically used to <a href="https://www.pcgamer.com/uk/how-game-sizes-got-so-huge-and-why-theyll-get-even-bigger/" rel="nofollow noreferrer">cache a lot of data</a>, thereby reducing time complexity (if only by a <span class="math-container">$O(1)$</span> factor).</p>
<p>The history of video games is roughly a transition from space complexity being the limiting factor to time complexity being the limiting factor, and there was a period when both were very important. For example, <a href="https://www.youtube.com/watch?v=pSHj5UKSylk" rel="nofollow noreferrer">Andy Gavin had to be very innovative with both</a>, but again a lot of it comes down to <span class="math-container">$O(1)$</span> factors.</p>

CC BY-SA 4.0
2020-08-16T09:01:41.093Z
2020-08-16T09:01:41.093Z
J.G.
<p>A look-up table algorithm is the extreme example of an algorithm where space is the limiting factor. In these types of algorithms you have an entry in a table for every possible input. This results in a time complexity of O(1) but the space complexity will be based upon the number of possible inputs. You can think of this as an analog to the old days where mathematics textbooks had charts for things like logarithms or sine/cosine etc.</p>
<p>
I have practically used these algorithms in embedded systems where the range of inputs was limited the range of a couple of  8-bit unsigned integers. I have also seen production code that had a look up table for a range of sine values of limited input precision.
<p>
This use case does not come up very often as input ranges are not commonly nicely range constrained or an output can depend on many variable or even worse if the order of the inputs matters (think traveling salesman)

CC BY-SA 4.0
2020-08-14T17:58:10.183Z
2020-08-18T11:14:44.893Z
2020-08-18T11:14:44.893Z
CaptianObvious
<p>I think most non-trivial quantum algorithms fit the bill here as the space requirement to store complex amplitudes for an <span class="math-container">$n$</span> qubit system is <span class="math-container">$2^n$</span> in the general case.</p>

CC BY-SA 4.0
2020-08-20T01:33:30.850Z
2020-08-20T01:33:30.850Z
Attila Kun
<p>You may like to read about the <a href="https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff" rel="nofollow noreferrer">space-time tradeoff</a>. Generally speaking, it's a continuum of how far you're willing to go to strike a balance between space and efficiency.</p>
<p>From a practical perspective, just about any computational process can be drastically optimized with <a href="https://en.wikipedia.org/wiki/Memoization" rel="nofollow noreferrer">memoization</a> (lookup tables), <a href="https://en.wikipedia.org/wiki/Inline_expansion" rel="nofollow noreferrer">inlining</a>, and <a href="https://en.wikipedia.org/wiki/Loop_unrolling" rel="nofollow noreferrer">unrolling</a>. I would say just about all efficient algorithms ultimately boil down to the application of memoization at various points in the computational process. Inserting data into a lookup table is like pre-computing specific aspects of the problem. In the extreme case, you can completely cache any function to achieve <span class="math-container">$O(1)$</span> complexity, provided you're happy to precompute every possible input and use a lookup table of size <span class="math-container">$2^{\#input\ bits}$</span>.</p>
<p>We don't talk about compiler optimizations like inlining and unrolling very much in practice, but they are equally important for efficient computation. The compiler often ends up inflating the executable size in order to eliminate redundant conditional checks.</p>
<p>You could also view data compression as being a trade-off between time and space complexity. Totally uncompressed data can be loaded linearly with respect to its size. Compressed data takes <strong>at least</strong> that long since it had to load the final data into memory <em>and</em> account for any computational overhead associated with compression and decompression.</p>

CC BY-SA 4.0
2020-08-18T17:47:49.840Z
2020-08-18T19:25:05.093Z
2020-08-18T19:25:05.093Z
user1318416
<p>I remembering hearing that early suffix tree algorithms suffered from space constraints:</p>
<ul>
<li><p>Linear time, exponential space: <a href="https://pdfs.semanticscholar.org/d339/0f13eed511cde1116446e71c3d462fd6a004.pdf" rel="nofollow noreferrer">Linear Pattern Matching Algorithms (1973)</a></p>
</li>
<li><p>Linear time, quadratic space: <a href="https://people.clarkson.edu/%7Emol/downloads/EE569/suffixTree.pdf" rel="nofollow noreferrer">A Space-Economical Suffix Tree Construction Algorithm (1976)</a></p>
</li>
</ul>
<p>The space (obviously) isn't fully written to, but must be allocated in their models of computation to ensure the time complexities they're trying to achieve.</p>
<p><em><strong>Unfortunately</strong></em>, these examples are the only info I have from old notes I have lying around, and I'm not currently clear on which precise part of each paper each one refers to. Hopefully they're correct, but if someone has more info, please help me update this answer.</p>

CC BY-SA 4.0
2020-08-15T00:30:16.793Z
2020-08-15T00:30:16.793Z
user541686
<p>There are at least a few areas in practice I can think of:</p>
<ol>
<li><p>Lots of games are PSPACE-hard, meaning you'll necessarily need a lot of space to play them optimally. See a table here: <a href="https://en.wikipedia.org/wiki/Game_complexity" rel="nofollow noreferrer">Wikipedia – Game complexity</a></p>
</li>
<li><p>The notion of &quot;memory-hard functions&quot; was developed as functions that are precisely designed to require large space to compute so that &quot;technological shortcuts&quot; can't allow an adversary to compute them more efficiently than expected, in other words, when hardness should translate to needing more real physical materials. They're of immense use in cryptography, especially for proof of work primitives in cryptocurrency. See <a href="https://en.wikipedia.org/wiki/Memory_hard_function" rel="nofollow noreferrer">Wikipedia – Memory hard function</a>.</p>
</li>
<li><p>In machine learning, space can be a limiting factor. Among the provable results, the <a href="https://arxiv.org/abs/1602.05161" rel="nofollow noreferrer">recent work by Ran Raz</a> stands out.</p>
</li>
</ol>

CC BY-SA 4.0
2020-08-13T18:51:28.603Z
PSPACE-hardness does not denote that the problem requires a lot of space: there are PSPACE-complete problems that can be solved in linear space. I would say PSPACE-completeness denotes the exact opposite: problems that probably require exponential time, but only polynomial space.
Laakeri
CC BY-SA 4.0
2020-08-13T19:30:13.170Z
Linear space is a lot of space :)
Mahdi Cheraghchi
CC BY-SA 4.0
2020-08-13T18:20:20.010Z
2020-08-16T20:21:28.230Z
2020-08-16T20:21:28.230Z
Mahdi Cheraghchi
<p>Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do, whereas time is only a factor if you're 'impatient.'</p>
<p>Preferably something practical.</p>

CC BY-SA 4.0
2020-08-13T20:09:15.050Z
Of course the whole field of streaming algorithms is predicated on not being able to store  the input. For instance packets going through a high-speed switch. You can afford to do linear time in terms of packets by examining each as it passed through but cannot store all of them. This may not be what you wanted but very well motivated from practice.
Chandra Chekuri
CC BY-SA 4.0
2020-08-14T09:18:39.683Z
I would assume such an algorithm would be a poly (or above) space algorithm with low space reuse.
rus9384
CC BY-SA 4.0
2020-08-14T18:45:15.907Z
@user253751: Not generally, no. You can have zero latency with some non-streaming algorithms but that doesn't make them streaming algorithms (because they use too much space).
user541686
CC BY-SA 4.0
2020-08-14T18:48:53.813Z
*"Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory)"*... I get what you're attempting to say, but it's worth noting this is only kind-of true. For example, if you want to make a lookup table mapping every integer to some other value, the time complexity would be logarithmic in the input value (input N = log(N) bits), but the space complexity would be linear in the input value (exponential in the number of bits).
user541686
CC BY-SA 4.0
2020-08-14T20:04:13.260Z
@user541686 Wouldn't each mapping still require an operation, making it linear in N? I'm not clear why time complexity would be logarithmic in N/ linear in number of bits.
Adam Tolnay
CC BY-SA 4.0
2020-08-14T20:08:27.800Z
@AdamTolnay: It depends on your model of computation, but if you assume memory is random-access rather than linear-access, then it would be constant-time (as some assume). If you relax it a bit to make it more realistic, it'd be linear in the number of bits. e.g. the input is N (say, N = 5 = 101b), and you'd need to process each bit to figure out what ultimate slot to read. Linear-access memory might be more physically accurate given space & the speed of light, but in practice it's useless unless you're dealing with e.g. tape storage (and it kind of misses the point I'm trying to make).
user541686
CC BY-SA 4.0
2020-08-14T21:24:31.643Z
@user541686 Ok, I think I misunderstood before, I thought the algorithm was creating the lookup table. I understand the space complexity of such a lookup table is exponential in the number of bits, but wouldn't the algorithm that uses it be linear time in the number of bits, and use constant space? Even if the table is huge, the number of bits in my input doesn't affect space usage.
Adam Tolnay
CC BY-SA 4.0
2020-08-14T21:26:34.213Z
@AdamTolnay: The algorithm "using" it (i.e. putting stuff into it or retrieving stuff from it) might e.g. assume unwritten slots are already initialized to zero. In that way it actually *requires* that space, despite only writing to a portion of it. Of course you can design another algorithm that *doesn't* have this requirement, but (a) it would be slower, and (b) it would miss the point that *this* algorithm can still exist.
user541686
CC BY-SA 4.0
2020-08-14T21:49:07.720Z
@user541686 But assuming unwritten slots are initialized to zero doesn't actually use that space. I don't think an algorithm that sections off an arbitrarily large amount of space based on input size and does nothing with it can be said to have high space complexity.
Adam Tolnay
CC BY-SA 4.0
2020-08-14T22:06:44.307Z
@AdamTolnay: Here's an analogy: if I give you a \$100 check to a bank account that contains $100, am I "using" the money in that bank account, or should I consider it unused? Would it be honest for me to give out 100 of those checks backed by the same \$100? If it turns out there's only \$50 in the account, could you honestly say that's a \$100 check if you pay someone with it? You can get into a pointless semantics debate over the meaning of "use", but that has no effect on the fact that you *do* need to set aside the full space for it, or it'll misbehave.
user541686
CC BY-SA 4.0
2020-08-14T22:37:25.487Z
@user541686 I'm not an expert, but the meaning of "use" isn't trivial when talking about complexity. If "use" means "overwrite a bit," as I suspect it would, then I can't see how space complexity can be higher than time complexity, as doing so requires time.
Adam Tolnay
CC BY-SA 4.0
2020-08-14T23:39:42.147Z
@AdamTolnay: Like I said: you can get into a pointless semantics debate over the meaning of "use" (and people define it in different ways depending on what's interesting in the given context), but your interpretation has no effect on the fact that *you **do** need to allocate the full (exponentially-sized) space to such an algorithm*, or it *will* misbehave. You were asking me to clarify, and I expect it should be pretty clear at this point what I meant when I said what you wrote is "kind-of" true, so I'm not going to continue arguing semantics.
user541686
CC BY-SA 4.0
2020-08-15T00:02:28.500Z
@user541686 Okay, thanks for the discussion, I'm obviously still learning.
Adam Tolnay
CC BY-SA 4.0
2020-08-15T12:52:13.050Z
Searching for "matching" (for example duplicate) entries in a large database could be an example: The whole database must be loaded into RAM to do this.
Martin Rosenau
CC BY-SA 4.0
2020-08-15T14:30:06.857Z
Not an algorithm with practical application per se, but the [Hashlife](https://en.wikipedia.org/wiki/Hashlife) algorithm for computing simulations of [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life) in logarithmic time requires a large amount of space for high-entropy patterns, so much so that decent optimizations of it require a dedicated garbage collector to remove unused nodes from the quadtree.
Patrick Roberts
CC BY-SA 4.0
2020-08-16T17:49:31.397Z
@ rus9384 When thinking of space complexity the input is considered read-only, otherwise one cannot define sub-linear space complexity classes such as log-space.
Chandra Chekuri
CC BY-SA 4.0
2020-08-19T16:28:31.087Z
An underlying reason why examples are hard to find is that the number of  operations per minute and storage bits in a personal computer are both roughly in the same order of magnitude, let's say around 10^11.

If the standard number of operations per minute was e.g. 10^20 instead, then space would be the clear barrier for algorithms that use linear time and space.
Abel Molina
<time-complexity><space-complexity>
What are some algorithms where space complexity tends to be the limiting factor in practice?
Adam Tolnay
# What are some algorithms where space complexity tends to be the limiting factor in practice?

(Asked by: username_0 on 2020-08-13)

Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do, whereas time is only a factor if you're 'impatient.'

Preferably something practical.

**Tags:** time-complexity, space-complexity

> **Comments:**
> **username_1**: Of course the whole field of streaming algorithms is predicated on not being able to store  the input. For instance packets going through a high-speed switch. You can afford to do linear time in terms of packets by examining each as it passed through but cannot store all of them. This may not be what you wanted but very well motivated from practice.  
> **username_2**: I would assume such an algorithm would be a poly (or above) space algorithm with low space reuse.  
> **username_3**: @user253751: Not generally, no. You can have zero latency with some non-streaming algorithms but that doesn't make them streaming algorithms (because they use too much space).  
> **username_3**: *"Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory)"*... I get what you're attempting to say, but it's worth noting this is only kind-of true. For example, if you want to make a lookup table mapping every integer to some other value, the time complexity would be logarithmic in the input value (input N = log(N) bits), but the space complexity would be linear in the input value (exponential in the number of bits).  
> **username_0**: @username_3 Wouldn't each mapping still require an operation, making it linear in N? I'm not clear why time complexity would be logarithmic in N/ linear in number of bits.  
> **username_3**: @AdamTolnay: It depends on your model of computation, but if you assume memory is random-access rather than linear-access, then it would be constant-time (as some assume). If you relax it a bit to make it more realistic, it'd be linear in the number of bits. e.g. the input is N (say, N = 5 = 101b), and you'd need to process each bit to figure out what ultimate slot to read. Linear-access memory might be more physically accurate given space & the speed of light, but in practice it's useless unless you're dealing with e.g. tape storage (and it kind of misses the point I'm trying to make).  
> **username_0**: @username_3 Ok, I think I misunderstood before, I thought the algorithm was creating the lookup table. I understand the space complexity of such a lookup table is exponential in the number of bits, but wouldn't the algorithm that uses it be linear time in the number of bits, and use constant space? Even if the table is huge, the number of bits in my input doesn't affect space usage.  
> **username_3**: @AdamTolnay: The algorithm "using" it (i.e. putting stuff into it or retrieving stuff from it) might e.g. assume unwritten slots are already initialized to zero. In that way it actually *requires* that space, despite only writing to a portion of it. Of course you can design another algorithm that *doesn't* have this requirement, but (a) it would be slower, and (b) it would miss the point that *this* algorithm can still exist.  
> **username_0**: @username_3 But assuming unwritten slots are initialized to zero doesn't actually use that space. I don't think an algorithm that sections off an arbitrarily large amount of space based on input size and does nothing with it can be said to have high space complexity.  
> **username_3**: @AdamTolnay: Here's an analogy: if I give you a \$100 check to a bank account that contains $100, am I "using" the money in that bank account, or should I consider it unused? Would it be honest for me to give out 100 of those checks backed by the same \$100? If it turns out there's only \$50 in the account, could you honestly say that's a \$100 check if you pay someone with it? You can get into a pointless semantics debate over the meaning of "use", but that has no effect on the fact that you *do* need to set aside the full space for it, or it'll misbehave.  
> **username_0**: @username_3 I'm not an expert, but the meaning of "use" isn't trivial when talking about complexity. If "use" means "overwrite a bit," as I suspect it would, then I can't see how space complexity can be higher than time complexity, as doing so requires time.  
> **username_3**: @AdamTolnay: Like I said: you can get into a pointless semantics debate over the meaning of "use" (and people define it in different ways depending on what's interesting in the given context), but your interpretation has no effect on the fact that *you **do** need to allocate the full (exponentially-sized) space to such an algorithm*, or it *will* misbehave. You were asking me to clarify, and I expect it should be pretty clear at this point what I meant when I said what you wrote is "kind-of" true, so I'm not going to continue arguing semantics.  
> **username_0**: @username_3 Okay, thanks for the discussion, I'm obviously still learning.  
> **username_4**: Searching for "matching" (for example duplicate) entries in a large database could be an example: The whole database must be loaded into RAM to do this.  
> **username_5**: Not an algorithm with practical application per se, but the [Hashlife](https://en.wikipedia.org/wiki/Hashlife) algorithm for computing simulations of [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life) in logarithmic time requires a large amount of space for high-entropy patterns, so much so that decent optimizations of it require a dedicated garbage collector to remove unused nodes from the quadtree.  
> **username_1**: @ username_2 When thinking of space complexity the input is considered read-only, otherwise one cannot define sub-linear space complexity classes such as log-space.  
> **username_6**: An underlying reason why examples are hard to find is that the number of  operations per minute and storage bits in a personal computer are both roughly in the same order of magnitude, let's say around 10^11.  If the standard number of operations per minute was e.g. 10^20 instead, then space would be the clear barrier for algorithms that use linear time and space.  

---

## 12 answers

### Answer by username_7 on 2020-08-13. Score: 19

Most computations in algebraic geometry / commutative algebra.

Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes. I think one of the first papers to look at this was Bayer & Mumford "[What can be computed in algebraic geometry?](https://arxiv.org/abs/alg-geom/9304003)".

(FWIW, my recent experience with these programs has been that there is a trichotomy: either the answer returns in (1) seconds, (2) a few minutes, or (3) so long that you give up / so much memory that it crashes.)


---

### Answer by username_8 on 2020-08-15. Score: 8

Dynamic programming is probably a general case of this but one specific, practically relevant and illustrative example is (global) [pairwise sequence alignment](https://en.wikipedia.org/wiki/Sequence_alignment#Pairwise_alignment) using the [Needleman–Wunsch algorithm](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm), which has both time and space complexity $\mathcal O(nm)$.

When applied to mammalian whole-genome alignments, this would naïvely require in the order of exabytes of space. Even bacterial genome alignments still require terabytes. By contrast, there’s a [clever variation of the algorithm due to Hirshberg](https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm) that uses divide & conquer to require only linear space ($\mathcal O(\min\{n,m\})$). This algorithm is also faster in practice (because it reduces the search space) but even if it didn’t improve the runtime it would still be practically feasible, whereas Needleman and Wunsch’s algorithm has prohibitive space requirements for all but small sequences.


---

### Answer by username_9 on 2020-08-13. Score: 8

My go-to answer for this (the one I use in undergraduate algorithms classes) is the Bellman–Held–Karp dynamic programming algorithm for the traveling salesperson problem (<https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm>). It's not the choice in practice for this problem (instead, branch-and-cut methods like in CONCORDE are faster) but it has the best proven time guarantees for the general problem, and its $O(n^2 2^n)$ time and $O(n2^n)$ space are in the range to make the space bound the bottleneck. There are alternative algorithms using polynomial space but with a higher exponential time bound, roughly $4^n$.


---

### Answer by username_10 on 2020-08-13. Score: 8

In knowledge compilation, the task is to compile some set $A\subseteq \{0,1\}^n$ into a format such that various queries can then be answered in polynomial time. For example, you can "compile" the set of satisfying assignments to a CNF formula $\psi$ into a Binary Decision Diagram (a kind of directed acyclic labelled graph). Once this is (expensive) computation is done, one can then do many things cheaply that are usually expensive.

For example, one can count the satisfying assignments of a CNF formula in time linear in the size of this BDD graph. If you have compiled two CNFs $\phi,\psi$ into BDDs, then you can check whether $\phi\implies \psi$, and count $|\phi\wedge \psi|$, in time $\Theta(|\phi|\_{\text{BDD}}\cdot |\psi|\_{\text{BDD}})$. This is significant, because a BDD can be exponentially smaller than the set that it encodes: some formulas have an exponential number of satisfying assignments, but have a BDD of size only, say, $\mathcal{O}(n^2)$.
The BDD of any clause $(x\_1\vee x\_2\vee\cdots\vee x\_{k})$ has size only $\Theta(k)$, so after building the BDD of a formula $\phi$ BDD ***once***, one can then check for clausal entailment $\phi\implies (x\_1\vee x\_2\vee\cdots\vee x\_k)$, for any clause, very quickly, in time $\Theta(|\psi|\_{\text{BDD}}\cdot k)$. Normally these computations are $\#\text{P}$-Complete and $\text{NP}$-Complete, respectively.

In an ideal situation, we have the opportunity to build the BDD during "preprocessing time", and once we're done, we hear which query we are supposed to answer. Then the limiting factor is that the BDD may grow exponentially in size. This blowup was always unavoidable, of course: We are trying to do intractable computations in polynomial time, so the tradeoff that we make is that the representation is exponentially large. Fortunately, in practice, this exponential behaviour rarely happens, and many interesting functions and systems can be represented by surprisingly small BDDs. For example, formulas with small treewidth have small BDDs.

Another wonderful application: the set $A$ is be the set of reachable configurations of a piece of software, or the reachable positions in chess. This is how BDDs made their debut: One can do exhaustive search on the state space of a program by compiling it into a BDD, and then one checks, for example, whether that set contains an element in which the program counters of two threads are in the same critical section. This last predicate is a simple formula with a small BDD, so intersection checking is fast.

Since the introduction of BDDs in 1986 [1], a large zoo of new diagrams have sprung up for this purpose: ZDDs, Tagged BDDs, SDDs, d-DNNFs. They make time/space tradeoffs: They are more compact, but support less queries. A good (but slightly out-of-date) overview is *A knowledge compilation map* [2]. All these diagrams are ultimately Boolean circuits, so finding out which ones are more compact than others is a difficult question of circuit lower bounds, so is part of computational complexity theory.

Of course BDDs are not always the answer, and modern model checking seems to favour SAT-based approaches, but Bryant's paper has 12k citations, so it is safe to say that people have found some uses for them.

[1] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.

[2] Darwiche, Adnan, and Pierre Marquis. "A knowledge compilation map." Journal of Artificial Intelligence Research 17 (2002): 229-264.


---

### Answer by username_1 on 2020-08-13. Score: 5

One example is multicommodity flow problems via Simplex method. In these problems we have a graph $G=(V,E)$ with $n$ nodes and $m$ edges and $K$ commodities. The number of variables is $Km$ (one per commodity and edge pair) and the number of constraints is roughly $m$. Now if you try to run the flow problem via simplex based algorithms then the incidence matrix is too large and inverting it creates a dense matrix which does not often fit in memory even though the initial problem is of reasonable size. This is one reason people use column generation and approximate iterative methods.

> **Comments:**
> **username_1**: I would think that the issue of memory would also be relevant to interior point methods.  

---

### Answer by username_11 on 2020-08-13. Score: 5

I don't know if the space complexity of this problem is *limiting* in practice (I have not personally run experiments to verify this, moreover I don't know anyone who needs to solve exact SVP in practice --- approximating it to some polynomial approx factor is already sufficient to break cryptography), but algorithms solving the Shortest Vector Problem in $n$-dimensional integer lattices fall into a few different classes:

1. [Enumeration](http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Enum.html) methods: $O(n^n)$ time, poly space
2. [Sieving](http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Sieve.html) methods: exponential time, exponential space, and randomized
3. [Voronoi Cell Computations](http://cseweb.ucsd.edu/%7Edaniele/LatticeLinks/Voronoi.html): exponential time, exponential space

This is to say all known exact SVP algorithms with provable running time $2^{O(n)}$ use exponential space, and algorithms with polynomial space usage have running time $2^{\omega(n)}$.


---

### Answer by username_12 on 2020-08-16. Score: 4

With this question we actually have to worry about [$O(1)$ factors](https://en.wikipedia.org/wiki/Analysis_of_algorithms#Constant_factors), because as you point out time can't be little o of space, but it can be much less demanding as a fraction of our hardware's abilities. A historical example, in which many algorithms could be discussed to make the point, would be old-school video games. I won't go into much detail here, but will lean on links; for now, it suffices to say it's mostly been about reducing the redundancy in data, sometimes [caring literally about every single bit](https://retrocomputing.stackexchange.com/questions/11476/how-did-satoru-iwata-compress-pokemon-gs-to-fit-two-regions-on-a-single-cartridg).

Nowadays, you can afford to give every pixel independent 24-bit colour in every frame. But [there was a time](https://www.youtube.com/watch?v=Tfh0ytz8S0k) you couldn't even achieve 2-bit colour that way, due to limited RAM. The reason that's no longer true is because RAM has grown much more in the last 40 years or so than screen resolution has. There were similar issues [with audio](https://www.youtube.com/watch?v=q_3d1x2VPxk).

The same period has also seen hardware expand how large the whole game can be, which may not sound like an algorithm detail, but it is because (1) game developers used to have to do all sorts of inventive things to do all they could with memory (here's a [modern take](https://www.youtube.com/watch?v=ZWQ0591PAxM) on just a few of them) and (2) modern games' large size is typically used to [cache a lot of data](https://www.pcgamer.com/uk/how-game-sizes-got-so-huge-and-why-theyll-get-even-bigger/), thereby reducing time complexity (if only by a $O(1)$ factor).

The history of video games is roughly a transition from space complexity being the limiting factor to time complexity being the limiting factor, and there was a period when both were very important. For example, [Andy Gavin had to be very innovative with both](https://www.youtube.com/watch?v=pSHj5UKSylk), but again a lot of it comes down to $O(1)$ factors.


---

### Answer by username_13 on 2020-08-14. Score: 3

A look-up table algorithm is the extreme example of an algorithm where space is the limiting factor. In these types of algorithms you have an entry in a table for every possible input. This results in a time complexity of O(1) but the space complexity will be based upon the number of possible inputs. You can think of this as an analog to the old days where mathematics textbooks had charts for things like logarithms or sine/cosine etc.

I have practically used these algorithms in embedded systems where the range of inputs was limited the range of a couple of 8-bit unsigned integers. I have also seen production code that had a look up table for a range of sine values of limited input precision.

This use case does not come up very often as input ranges are not commonly nicely range constrained or an output can depend on many variable or even worse if the order of the inputs matters (think traveling salesman)


---

### Answer by username_14 on 2020-08-20. Score: 1

I think most non-trivial quantum algorithms fit the bill here as the space requirement to store complex amplitudes for an $n$ qubit system is $2^n$ in the general case.


---

### Answer by username_15 on 2020-08-18. Score: 1

You may like to read about the [space-time tradeoff](https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff). Generally speaking, it's a continuum of how far you're willing to go to strike a balance between space and efficiency.

From a practical perspective, just about any computational process can be drastically optimized with [memoization](https://en.wikipedia.org/wiki/Memoization) (lookup tables), [inlining](https://en.wikipedia.org/wiki/Inline_expansion), and [unrolling](https://en.wikipedia.org/wiki/Loop_unrolling). I would say just about all efficient algorithms ultimately boil down to the application of memoization at various points in the computational process. Inserting data into a lookup table is like pre-computing specific aspects of the problem. In the extreme case, you can completely cache any function to achieve $O(1)$ complexity, provided you're happy to precompute every possible input and use a lookup table of size $2^{\#input\ bits}$.

We don't talk about compiler optimizations like inlining and unrolling very much in practice, but they are equally important for efficient computation. The compiler often ends up inflating the executable size in order to eliminate redundant conditional checks.

You could also view data compression as being a trade-off between time and space complexity. Totally uncompressed data can be loaded linearly with respect to its size. Compressed data takes **at least** that long since it had to load the final data into memory *and* account for any computational overhead associated with compression and decompression.


---

### Answer by username_3 on 2020-08-15. Score: 0

I remembering hearing that early suffix tree algorithms suffered from space constraints:

* Linear time, exponential space: [Linear Pattern Matching Algorithms (1973)](https://pdfs.semanticscholar.org/d339/0f13eed511cde1116446e71c3d462fd6a004.pdf)
* Linear time, quadratic space: [A Space-Economical Suffix Tree Construction Algorithm (1976)](https://people.clarkson.edu/%7Emol/downloads/EE569/suffixTree.pdf)

The space (obviously) isn't fully written to, but must be allocated in their models of computation to ensure the time complexities they're trying to achieve.

***Unfortunately***, these examples are the only info I have from old notes I have lying around, and I'm not currently clear on which precise part of each paper each one refers to. Hopefully they're correct, but if someone has more info, please help me update this answer.


---

### Answer by username_16 on 2020-08-13. Score: 0

There are at least a few areas in practice I can think of:

1. Lots of games are PSPACE-hard, meaning you'll necessarily need a lot of space to play them optimally. See a table here: [Wikipedia – Game complexity](https://en.wikipedia.org/wiki/Game_complexity)
2. The notion of "memory-hard functions" was developed as functions that are precisely designed to require large space to compute so that "technological shortcuts" can't allow an adversary to compute them more efficiently than expected, in other words, when hardness should translate to needing more real physical materials. They're of immense use in cryptography, especially for proof of work primitives in cryptocurrency. See [Wikipedia – Memory hard function](https://en.wikipedia.org/wiki/Memory_hard_function).
3. In machine learning, space can be a limiting factor. Among the provable results, the [recent work by Ran Raz](https://arxiv.org/abs/1602.05161) stands out.

> **Comments:**
> **username_17**: PSPACE-hardness does not denote that the problem requires a lot of space: there are PSPACE-complete problems that can be solved in linear space. I would say PSPACE-completeness denotes the exact opposite: problems that probably require exponential time, but only polynomial space.  
> **username_16**: Linear space is a lot of space :)  

---

