Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
0
votes
0answers
6 views

Configuration of a space bounded turing machine

A configuration of a turing machine is defined as the following: an ordered triple (x, q, k) ∈ Σ∗ × K × N, where x denotes the string on the tape, q denotes the machine's current state, and k denotes ...
1
vote
0answers
21 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
1
vote
1answer
137 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space reductions ...
1
vote
1answer
30 views

Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps ...
1
vote
0answers
12 views

What is the space-complexity of a boolean first-order query?

I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant). ...
5
votes
1answer
50 views

Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow ...
1
vote
0answers
36 views

Complexity in time and memory for graph search algorithm

I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
1
vote
2answers
353 views
2
votes
2answers
42 views

Algorithmic problem with many different time/space complexity solutions

I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ...
1
vote
1answer
59 views

Is in-place run length encoding possible in O(1) space given that the output is shorter than the input?

This is inspired by a problem from here. This is the approximate form of the problem: Given a string like "aaaa777cbb" (10 symbols long), run length encode it in-place to a string like "...
3
votes
3answers
210 views

Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
1
vote
0answers
25 views

A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
2
votes
1answer
83 views
2
votes
2answers
32 views

Finding the most frequent element assuming $\Theta(n)$ frequency

We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...
0
votes
1answer
544 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
1
vote
2answers
241 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
1
vote
1answer
30 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
2
votes
0answers
67 views

Enumerating points on the integer lattice, within a sphere, sorted by angle, in O(1) space

Inspired by this StackOverflow question: https://stackoverflow.com/questions/63346135 (it was not clearly presented, and got closed) Let's say I wanted to enumerate all the 3D points on the integer ...
1
vote
2answers
50 views

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
1
vote
0answers
39 views

Complexity of find histogram bins vs convex hull

For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order. Meanwhile What’s the complexity of finding the histogram bin edges of k ...
0
votes
0answers
29 views

Is $DSPACE(n^8) \subset NSPACE(n^5)$?

I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold. I know from Savitch's Theorem that: $$ NSPACE(n^5) \subseteq DSPACE((n^5)^2) = DSPACE(n^{10})$$ If the ...
0
votes
1answer
34 views

Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

As said in the title, i am quite curious wether NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n)) I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n)) due to linear space reduction (i.e. ...
1
vote
0answers
16 views

Configurations and CNF formula for neighboring configuration

A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its ...
0
votes
2answers
79 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
2
votes
1answer
58 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
0
votes
1answer
13 views

one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...
5
votes
1answer
1k views

Is this in-place merge algorithm efficient or not?

I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head ...
0
votes
0answers
18 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible... As an attempt, isn't the proof ...
1
vote
1answer
86 views

Is every linear language in NL?

I wonder if all the linear languages are in NL? I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
1
vote
1answer
17 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have $$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$ Am wondering, what happens if $S(n)$ is fully time-...
0
votes
0answers
25 views

Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
3
votes
2answers
198 views

Is FACTORIZATION or PRIMES known to be in LOGSPACE

Are the integer factorization and PRIMES known to be in LOGSPACE? Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known ...
0
votes
1answer
36 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
0
votes
0answers
46 views

Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
2
votes
2answers
75 views

Logarithmic space verifier with unbounded witness

this is a HW question, but its considered a bonus question so I'd appreciate a direction. Definitions: The actual question: **Images taken from HW in TAU Complexity course by Amnon Ta-Shma. My ...
1
vote
1answer
44 views

Worst simultaneous blowup when converting to CNF and DNF

I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the ...
1
vote
1answer
24 views

Log space reduction from STCONN to CYCLE

I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.
1
vote
1answer
22 views

Importance of space constructability in time space relation in complexity

I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem. Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $...
6
votes
2answers
1k views

Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $ \Omega (\log\log n) $ space complexity. I'm looking for an example of a language which is $ \Theta (\log\log n) $ space complexity (...
5
votes
2answers
69 views

Does time or space complexity of arithmetic operations get affected by the number of digits?

Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size ...
0
votes
1answer
43 views

Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
0
votes
1answer
73 views

Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

The solution to this problem can be found here. It says: To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of ...
1
vote
1answer
29 views

Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

Let n be an even integer. Let I be an input of length n. Positions start at 0: the first ...
0
votes
1answer
25 views

Does checking the middle bit of an input require a log(n) space pointer?

Let n be an even integer. Let i be an input of length n. Positions start at 0: the first ...
0
votes
0answers
20 views

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

Suppose I nondeterministically walk around in a graph with n vertices. When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices. There are (n choose n/2) different combinations of ...
0
votes
1answer
26 views

Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?

Let k be a positive even integer. Given a list of (k choose k/2) k-sequences, each with an ...
0
votes
0answers
36 views

Does this imply checking a candidate Hamiltonian Path solution can be done in logspace?

Assume vertices are integers base 2. Smallest vertex is 1. There are n vertices. Our input is: the number of vertices (n expressed in log(n) bits - ...
1
vote
1answer
25 views

Lower bound time complexity for obtaining an arbitrary entry in a hashtable

I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable, the algorithm should return a pointer to an arbitrary nonempty entry in the ...
1
vote
2answers
256 views

Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ There are two possible approaches to this exercise: Solving cycle in undirected graph in log ...

1
2 3 4 5
8