# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

387 questions
Filter by
Sorted by
Tagged with
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 ...
55 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 "...
190 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 ...
72 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: ...
28 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 (...
61 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 ...
42 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 ...
69 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 ...
28 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 ...
21 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 ...
19 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 ...
33 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 - ...
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 ...
243 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 ...
14 views

### Big O notation space/time

I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read ...
93 views

### Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says: Let $L\in NPSPACE$. Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...
49 views

### Find nearest neighbour in a radius

I have a set of points A in my space (geo points but I can assume they are on a 2D plane). I have another set of points B. For every point in B I want to find every point in A inside a radius R with ...
410 views

### $UCYCLE$ is in $L$

I'm trying to understand the log-space algorithm for $$UCYCLE = \{ \langle G \rangle \ | \text{ G is an undirected graph containing a cycle} \}$$ The basic idea is traversing from every $v\in V$, ...
66 views

### Nondeterministic Logarithmic-space in directed graph

I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the ...
Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem. I have already successfully demonstrated that this problem $\in NL$. But I'm stuck on how to take it ...