The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
882 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 ...
4
votes
0answers
271 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 ...
4
votes
1answer
102 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 ...
2
votes
0answers
36 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 ...
2
votes
0answers
36 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 ...
2
votes
0answers
60 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 ...
2
votes
0answers
47 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 ...
2
votes
0answers
208 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 ...
2
votes
0answers
138 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 ...
2
votes
0answers
57 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 ...
2
votes
0answers
597 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 ...
2
votes
0answers
312 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 ...
1
vote
1answer
23 views

Space efficient representation of Regular graphs

Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time....
1
vote
0answers
31 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 ...
1
vote
1answer
114 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
0answers
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 ...
1
vote
0answers
35 views

Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?

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(...
1
vote
0answers
21 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
1
vote
0answers
49 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 ...
1
vote
0answers
25 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...)
1
vote
0answers
204 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
1
vote
0answers
37 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, ...
1
vote
0answers
32 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)
1
vote
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 ...
1
vote
0answers
100 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 ...
1
vote
0answers
431 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)$ ...
1
vote
0answers
191 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 \...
1
vote
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 ...
1
vote
0answers
599 views

Space Complexity

This particular code is written in C. ...
1
vote
0answers
173 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 ...
1
vote
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 ...
1
vote
0answers
107 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 ...
1
vote
1answer
162 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 ...
0
votes
0answers
39 views

Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
0
votes
1answer
47 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 ...
0
votes
0answers
33 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 ...
0
votes
0answers
34 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 ...
0
votes
0answers
20 views

Analysis Or Review Of Article “Table Design In Dynamic Programming”

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
0
votes
0answers
43 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
0
votes
0answers
81 views

Time complexity of well know constraint satisfaction problem algorithms with heuristics

I have know that complexity of csp algorithms as follow: Backtracking algorithm for constraint processing space:O(n) ,Time :O(expn) Backjumping algorithm for constraint satisfaction problem ...
0
votes
0answers
39 views

Is there a known lower bound on the time/space complexity of DFA minimization?

I've read the Wikipedia page on the topic, but there's no mention of a lower bound on the time complexity, and there's no mention of space complexity at all.
0
votes
0answers
44 views

Space complexity for accepting word decision problem of DFAs

It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can ...
0
votes
1answer
310 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'. ...
0
votes
0answers
215 views

Space complexity of Coin change with memoization

I've read conflicting answers for the space complexity of the top down implementation w/ memoization for the classic coin change problem. Would this be O(N * M) space as Interview Cake says https://...
0
votes
0answers
96 views

show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
0
votes
0answers
77 views

Generalized Geography problem time and space complexity

We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more ...
0
votes
0answers
63 views

Row-Column agnostic Matrix datastructure

Due to the linear nature of computer memory, row-major and column-major matrices have different performance for row- vs. column access. The obvious solution would be to keep two copies of the same ...
0
votes
0answers
128 views

Proving SAT is in L

How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.
0
votes
0answers
136 views

Alternating Turing Machine: Why one cannot generalize the proof of AL = P?

In their paper "Alternation" Chandra et al. show how an Alternating Turing Machine can simulate a Deterministic Turing Machine with time-complexity $t(n)$ using only $\log(t(n))$ space what implies $P ...
0
votes
0answers
42 views

P-complete problem due to logspace reductions. What does it mean?

Prove that problem $A$ is complete in $P$ due to reductions computed in logarythmic space How to understand this statement ? What should be shown ? For me: 1. $A$ is in $P$. 2. Each problem in $...