Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
1
vote
1answer
25 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
2
votes
0answers
54 views

Enumerating points on the integer lattice, within a sphere, sorted by angle, in O(1) space

Inspired by this StackOverflow question: https://stackoverflow.com/questions/63346135 (it was not clearly presented, and got closed) Let's say I wanted to enumerate all the 3D points on the integer ...
1
vote
2answers
43 views

What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
1
vote
0answers
43 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: ...
1
vote
0answers
35 views

Complexity of find histogram bins vs convex hull

For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order. Meanwhile What’s the complexity of finding the histogram bin edges of k ...
0
votes
0answers
24 views

Is $DSPACE(n^8) \subset NSPACE(n^5)$?

I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold. I know from Savitch's Theorem that: $$ NSPACE(n^5) \subseteq DSPACE((n^5)^2) = DSPACE(n^{10})$$ If the ...
0
votes
1answer
28 views

Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

As said in the title, i am quite curious wether NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n)) I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n)) due to linear space reduction (i.e. ...
1
vote
0answers
15 views

Configurations and CNF formula for neighboring configuration

A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its ...
0
votes
2answers
49 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
2
votes
1answer
48 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
0
votes
1answer
12 views

one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...
0
votes
0answers
17 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible... As an attempt, isn't the proof ...
1
vote
1answer
14 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have $$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$ Am wondering, what happens if $S(n)$ is fully time-...
1
vote
1answer
86 views

Is every linear language in NL?

I wonder if all the linear languages are in NL? I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
0
votes
0answers
25 views

Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
0
votes
0answers
41 views

Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
0
votes
1answer
32 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
2
votes
2answers
62 views

Logarithmic space verifier with unbounded witness

this is a HW question, but its considered a bonus question so I'd appreciate a direction. Definitions: The actual question: **Images taken from HW in TAU Complexity course by Amnon Ta-Shma. My ...
1
vote
1answer
19 views

Log space reduction from STCONN to CYCLE

I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.
1
vote
1answer
37 views

Worst simultaneous blowup when converting to CNF and DNF

I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the ...
1
vote
1answer
19 views

Importance of space constructability in time space relation in complexity

I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem. Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $...
0
votes
1answer
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 ...
1
vote
1answer
27 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 ...
0
votes
1answer
20 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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 - ...
1
vote
1answer
24 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 ...
1
vote
1answer
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 ...
4
votes
2answers
55 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 ...
0
votes
1answer
41 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 ...
-1
votes
1answer
69 views

The existence of a cycle in a directed graph is a NL-complete? [duplicate]

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 ...
1
vote
1answer
61 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 ...
1
vote
2answers
231 views

Logspace algorithm for balanced parentheses problem

Currently I want to learn the complexity of space, I read a few of the books on it. On this I encountered this example problem. I would just like to know how to show that the following problem $​\in L ...
2
votes
1answer
33 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 ...
4
votes
1answer
82 views

Query: Given a graph, is edge x in an optimal TSP tour?

Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph. It may be argued that ...
1
vote
1answer
297 views

Space complexity of Travelling Salesman Problem

I am having trouble coming up with the space complexity of the TSP algorithm. https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ To me the space complexity for the brute force is the ...
1
vote
1answer
43 views

Is $L \subset 1NL$ when $L \neq NL$? [closed]

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
2
votes
1answer
87 views

Time complexity for the 'Restore IP Addresses' problem

There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns ["...
1
vote
1answer
42 views

The characterization of a problem as PSPACE-complete is …?

Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-...
3
votes
1answer
128 views

Composition of functions computable in logspace

The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language: $\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\}$ It is ...
1
vote
0answers
24 views

Storing a configuration of nondeterministec machines in log space

In Sipser's book page 351: Recall that Savitch's theorem shows that we can convert nondeterministic TMs to deterministic TMs and increase the space complexity $f(n)$ by only a squaring, provided ...
2
votes
0answers
36 views

Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist

Hello and thank you for helping me understand the following: I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space. context: Defining ...
0
votes
1answer
27 views

How will I calculate the time and space complexity for this pyramid algo? [duplicate]

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345": ...
2
votes
0answers
24 views

Existence of a P-Complete language with space($\log\log n$) reduction

I have been reading and searching and I still cannot understand if there exists a language as following: Can a language be P-complete with respect to $\mathsf{Space}(\log \log n)$ reductions? ...
4
votes
0answers
41 views

Understanding an example of an EXP-SPACE Problem

I am trying to understand the example given here of an EXP-SPACE time decision problem. They write : An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular ...
2
votes
1answer
98 views

PSPACE-completeness of DFA intersection problem

Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness. It seems to me that I ...
0
votes
0answers
31 views

Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
1
vote
0answers
46 views

PSPACE-hardness of the unbounded puzzle

Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i,...
0
votes
1answer
68 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 ...

1
2 3 4 5
8