# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

491 questions
Filter by
Sorted by
Tagged with
41 views

### Why does storing an $n$-element array require $O(n)$ space?

This may seem to be a trivial question, but I am a bit stumbled by why people claim: $n$-element array requires $O(n)$ space Under what assumption does this statement hold? Is there an assumption in ...
97 views

### What else measures are used to compare algorithm efficiency apart from Time and Space complexities?

While Time Complexity is the measure of how an algorithm scales with respect to input size, Space Complexity on the other hand measures how much the memory scales as input changes. I see ...
59 views

### How to allocate memory for prime numbers

I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I ...
100 views

### Isn't allocating a same size array for result considered to be space complexity O(n)?

It is related to this question: https://leetcode.com/problems/product-of-array-except-self/ And assuming we cannot alter the original array, but have to allocate a same size array to store the results,...
52 views

### PSPACE≠co-NP?Is the statement true?

Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
14 views

### $A\in LSPACE \Longrightarrow CYCLE(A)\in LSPACE$

Let $A$ be a language and define $$CYCLE(A)= \{ yx | xy \in A \}$$ I need to prove, or disprove, $A\in LSPACE \Longrightarrow CYCLE(A)\in LSPACE$. First I tried to prove $CYCLE(A) \le_{L} A$ which ...
1 vote
38 views

### Lower Bound on Parity of Boolean Functions

Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
59 views

### Space efficient data structure to store precomputed All Nearest Neighbors in high dimensions

Seeking an indexing data structure that is smaller than quadratic in space. As part of an NLP algorithm using word embeddings of 300-dimensions, I am trying to improve the speed of Word Mover's ...
54 views

### ALL-NFA is PSPACE-complete

Show that $ALL-NFA$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $PSPACE-complete$. I've manged o prove that it is $PSPACE$. It is easy to see that $\overline{ALL-NFA}\in NPSPACE$ (TM ...
1 vote
298 views

### Unions of PSPACE-comlete problems that are PSPACE-complete?

Let $A,B\subsetneq\Sigma^*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete? In ...
32 views

### What is the space complexity of deterministic real-time context-free languages?

The linear context-free languages are included in NL, and there exist linear languages that are NL-complete. On the other hand, the set of linear deterministic context-free languages is included in L. ...
74 views

### Base transcoding with minimum storage and complexity

I want to reversibly transcode arbitrary information (a digital signature), initially $n$ bits, into symbols in an alphabet with $s$ symbols, with little space loss. In my application‡ $s=45$. Thus I ...
27 views

### Are $\mathsf{L,NL}$ closed under reverse operation?

for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\}$. My question is, are $\mathsf{L,NL}$ closed under ...
46 views

### Proving the language 2-SIMPLE-PATH is in NL

The Question I define the language\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\...
13 views

711 views

82 views

### Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem

I was wondering whether someone could help me resolve an issue I have understanding the proof given for Savitch’s theorem in the Sipser text (3rd edition). The question I have is more or less ...
1 vote
88 views

### Implications of Savitch's theorem

I'm trying to figure out if the following statements are true: • Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$. • Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$. • ...
1 vote
24 views

### example of an NL-completeness reduction?

I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
1 vote
96 views

### Breakdown of the Space Hierarchy Theorem

Say that we have two deterministic space complexity classes $SPACE(n^k)$ and $SPACE(f(n))$ where $f(n) = n^{k-1}$ when $n$ is odd and $f(n) = n^{k+1}$ when $n$ is even. Obviously, if $f(n)$ were ...
51 views

### In search for a complete definition for write-only TMs / Tapes

In the following lines I will present my question, whose content is divided in two parts: Preparation and Actual . (1) — Preparation Regarding the formal definition of the (one tape) general Turing ...
1 vote
48 views

### Space-efficient way to prove that a data has been processed before

Suppose that I have a stream of data packets in the form of unsigned 64 bit integers. And I want to make sure that I am not processing the same packet content more than once. A way of doing this would ...
402 views

### Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?

My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
53 views

### Do tasks that take up more memory/space always take more time?

Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep ...
76 views

### Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $L \notin PSPACE$ over the alphabet {0,1} ...
85 views

### Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?

These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that ...
1 vote
36 views

### Graph based on strings of turing machine

For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
1 vote
114 views

### How do I find out what SPACE a language has?

I want to know how I can calculate/find out which SPACE a language has, because I don't get it. I have this definition Definition: Fix a function $f: \mathbb N → \mathbb N$. We say that a language $A$...
264 views

### Is NL closed under complemenrt?

I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L =...
677 views

### What are the fundamentals of calculating space complexity in loops?

Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I ...
158 views

### How do I determine the time and space complexity of the following algorithm?

I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication. ...
138 views

### Trivial Proof that EXP = PSPACE(im 99% sure i'm doing somthing wrong.)

Generalized chess is EXPTIME complete. Generalized chess is also PSPACE complete. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$ This proof is probably wrong. I want to know ...
81 views

### Randomized Algorithm Log-Space Exp-Time

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the ...
Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...