# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

392 questions
Filter by
Sorted by
Tagged with
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 ...
21 views

### Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
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 ...
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 ...
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). ...
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 ...
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....
353 views

### What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
26 views

Recursive ...
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 ...
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 "...
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?
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 ...
83 views

### what will be space complexity for snippet for(i=1 to n) int x=10;?

The space complexity of the code snippet given below: ...
32 views

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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 - ...
### 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 ...