Questions tagged [space-complexity]
Asymptotic analyses of the space needed to run algorithms.
491
questions
-1
votes
0
answers
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 ...
- 789
4
votes
1
answer
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 ...
0
votes
1
answer
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 ...
- 103
0
votes
1
answer
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,...
- 101
0
votes
1
answer
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
0
votes
0
answers
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 ...
- 261
1
vote
0
answers
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 ...
- 13
2
votes
1
answer
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 ...
- 251
0
votes
0
answers
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
1
vote
1
answer
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 ...
0
votes
0
answers
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. ...
- 1
5
votes
1
answer
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 ...
- 519
2
votes
0
answers
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 ...
- 141
2
votes
0
answers
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\;\...
- 145
0
votes
0
answers
13
views
is co-NSPACE(n^2) a strict subset of DSPACE(n^5)?
Is $co-NSPACE(n^2) \subsetneq DSPACE(n^5)?$
From Savitch theorem $co-NSPACE(n^2) \subset DSPACE(n^4) \implies co-NSPACE(n^2) \subset DSPACE(n^5) $
and as $ PSPACE = NPSPACE$ we can go further to $ ...
9
votes
4
answers
2k
views
Does an algorithm's space complexity include input?
Consider the Kadane's algorithm for finding maximum subarray within an array:
...
- 255
-3
votes
1
answer
38
views
NSPACE(n^2) and DSPACE(n^2) class problems
What problems belong in NSPACE(n^2) and DSPACE(n^2) class? Examples?
- 1
1
vote
2
answers
97
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 287
0
votes
4
answers
711
views
What is the point of Bloom's filter if its false positive rate is so high?
This and this agree that there will be near 100% false positive rate with Bloom's filter should number of elements in the set ($n$) be greater than the number of bits in the filter ($m$).
E.g. if $n=...
- 115
2
votes
0
answers
32
views
How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?
In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
- 21
3
votes
3
answers
939
views
A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity
Why is Solution 1 faster than Solution 2?
The input passed to both solutions:
...
- 131
0
votes
0
answers
27
views
What will be the Computational Complexity in terms of order O of the operations shown in the following figure
Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors.
So, first, I have to do a scalar multiplication with a vector ...
0
votes
1
answer
37
views
Confusion about NP vs. LINSPACE
I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
- 271
1
vote
1
answer
124
views
Why do we need to "allocate" an amount of space in the context of space-complexity?
In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146):
It
is tempting to say that sub-logarithmic space ...
- 3,622
1
vote
0
answers
11
views
How branching programs with small width are related to Turing machines with small space?
The complexity book by Arora and Barak mentions that "branching programs of constant width (reminiscent of a TM with O(1) bits of memory) seem inherently weak." I am not able to figure out ...
- 11
-4
votes
1
answer
75
views
what will be the space complexity of the following?
if two vectors are used for ex,
vector<vector> temp;
vector temp2;
then what will be the space complexity, will it be O(n) or O(n^2)?
1
vote
1
answer
96
views
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Given an undirected graph ...
- 401
2
votes
1
answer
116
views
Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.
This is similar to the notion ...
- 53
1
vote
1
answer
424
views
If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :
NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then
SAT is also PSPACE-hard. Since every language in PSPACE can be
reduced ...
1
vote
1
answer
195
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
- 125
2
votes
2
answers
52
views
Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,
The restrictions:
$...
- 21
0
votes
1
answer
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 ...
- 51
1
vote
1
answer
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)$.
• ...
- 413
1
vote
0
answers
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-...
- 2,469
1
vote
1
answer
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 ...
- 33
0
votes
0
answers
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 ...
- 61
1
vote
2
answers
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 ...
- 11
0
votes
2
answers
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 ...
- 325
0
votes
1
answer
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 ...
- 113
2
votes
1
answer
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} ...
- 21
0
votes
2
answers
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 ...
- 219
1
vote
0
answers
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 ...
- 103
1
vote
2
answers
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$...
- 73
3
votes
1
answer
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 =...
4
votes
1
answer
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 ...
- 43
0
votes
1
answer
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.
...
0
votes
1
answer
138
views
Trivial Proof that EXP = PSPACE(im 99% sure i'm doing somthing wrong.)
Generalized chess is EXPTIME complete[1]. Generalized chess is also PSPACE complete[2]. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$
This proof is probably wrong. I want to know ...
- 219
0
votes
1
answer
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 ...
0
votes
1
answer
38
views
Help in proving L-Completeness
I'm trying to prove that the following language is L-complete
A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's
So far I've managed ...
- 165
0
votes
0
answers
165
views
Space complexity for divide-and-conquer
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$ ...
- 101