# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

56 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
835 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 ...
88 views

### Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
270 views

### Space complexity of statistic functions

When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be ...
617 views

### Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
31 views

### Is PSPACE vs NEXPTIME known?

I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME. Is anything known about ...
34 views

### What is the computational complexity of the first-order theory of real arithmetic?

Tarski proved that the first-order theory of real-closed fields is decidable. Is the exact computational complexity known? The best upper bound I could find is EXPSPACE [1], where it is also ...
53 views

### Why is a pointer constant space?

If a pointer specifies a point in memory, would the amount of space a pointer takes not be dependent on how much memory it could possibly range over? So for example, if we have 4 locations of memory ...
46 views

### Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
200 views

### Natural logspace complete problems

After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult ...
135 views

### Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
54 views

### Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
561 views

### Sorting array with constant memory

Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell. So ...
310 views

### Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
6 views

### Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
30 views

### Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements: (i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$ (ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$ For the Space ...
89 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?
30 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 ...
27 views

The book I am reading is suggesting the following: Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(... 0answers 20 views ### Without using the Space Hierarchy Theorm is there any other way to prove that NL is not equal to PSPACE From what I know there is no alternate way that NL is not equal to PSPACE. If possible can you link a paper or some book recommendations to show that this is the case. Thank You Akash 0answers 48 views ### If problem A is logspace reducible to 2-SAT, is A in NL? I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL? If so, how does one ... 0answers 24 views ### How to check a graph diameter in LOGSPACE? Given a graph G, how can I check that its diameter doesn't exceed log(n) (n is the number of vertices)- by using only O(log(n)) space? (adjacency matrix doesn't seems to help...) 0answers 180 views ### What is the Space Complexity of Tail Recursive Quicksort? Looking at the following tail recursive quicksort pseudocode ... 0answers 36 views ### What does actually happens on tile hashing I am going through Richard Sutton book about Reinforcement Learning and I just encountered the tile coding method. I understood pretty well the principles, however, at the very end of the section, ... 0answers 31 views ### EXPTIME$\neq$EXPSPACE consequences? We know that$EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE$, where$EXPSPACE = DSPACE(2^{poly(n)})$. Question: Is known any consequences of$EXPTIME \neq EXPSPACE$? (nothing in complexity zoo or wikipedia) 0answers 24 views ### United space-time complexity of finite strings Let's consider bit string as a program for some computational model. If after$k$steps program represented by number$n$halts and outputs bit string$s$, then complexity of s is (n+1)*k. For example ... 0answers 95 views ### Complexity of emptiness checking for visibly pushdown automata? Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ... 0answers 430 views ### Is PSPACE closed under the following forall-there-exists construction? Suppose I have a language$L$(over alphabet$\Sigma$), such that $$w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w).$$ and I can give a turing machine that decides$P(x,y,w)$... 0answers 184 views ### Misunderstanding the Baker-Gill-Solovay oracle and obtaining$LOGSPACE^A=PSPACE^A$Baker, Gill and Solovay [1] gave an oracle$A$relative to which$P^A=PSPACE^A$. The oracle is the very simple$PSPACE^A$-Complete language $$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \... 0answers 40 views ### Naming for (memory near optimal) datastructres Assume that we wish to solve some problem that has a information theoretic memory lower bound of \mathcal B bits. In computer science, there are a few classes for data structures which are close to ... 0answers 582 views ### Space Complexity This particular code is written in C. ... 0answers 169 views ### Parallel time is sequential space Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the ... 0answers 526 views ### Examples of real world graphs that are too big for a single commodity-type machine I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ... 0answers 103 views ### General object recognition versus specific object recognition I have a question about the difference between general object detectors and specific object detectors. By specific object detectors, I'm referring to classifiers/object recognizers that are built to ... 1answer 157 views ### Show that problem is PSPACE-complete - path in directed graph I have a following problem: Given n and graph of size 2^n, and circuit with 2n input gates. Directed edge between k and l exists iff only and only we encode k and l as bits and launch ... 1answer 41 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 ... 0answers 30 views ### Logarithmic reduction from Clique to Half-Clique so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises. I understand how to make a poly-reduction but I am not able ... 0answers 33 views ### Is the language L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M uses m space on input x$$\}$ decidable?

I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
150 views

### Difference between auxiliary space v/s space complexity

I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$...