# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

378 questions
Filter by
Sorted by
Tagged with
205 views

### Non-existence of PSPACE-hard unary language

I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard. Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it ...
39 views

### Time and space complexity of a recursive problem (code included)

I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from ...
860 views

### Is Breadth First Search Space Complexity on a Grid different?

Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning: For example, the flood fill question is described here: https://www....
101 views

### What is space complexity of shrinking one array to increase another?

Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, ...
52 views

335 views

### What's after EXPSPACE?

As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE. Thinking about this question, I came up with a ...
597 views

### Max number of configurations of a Turing Machine

I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$. Is this because a configuration consists of a state, a ...
419 views

882 views

### What algorithm to use for this subset sum problem

I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now. I have ...
55 views

### STCON in L using matrix multipication algorithm?

I'm trying to understand why the following is incorrect. Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-...