Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
2
votes
0answers
17 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
2
votes
5answers
240 views

Find two non-overlapping subarrays, with total sum equal to k

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total ...
1
vote
1answer
54 views

If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$

I have been given an assignment that I'm having a very hard time understanding. The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
1
vote
0answers
17 views

Complexity classes and "local pre-processing"

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
0
votes
1answer
31 views

Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
0
votes
0answers
17 views

Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...
1
vote
1answer
70 views

Another version of Geography Game

The classic definition of normal “Geography Game” is the following: Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (...
1
vote
2answers
41 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
0
votes
0answers
28 views

What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
1
vote
1answer
39 views

What is the space-complexity of the Newton-Raphson algorithm?

What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.
0
votes
1answer
44 views

What is the true space-complexity of saving all divisors, because $N$ can have more divisors than the length of $N$?

$6983776800$ in binary has 33 bits but has $2034$ positive divisors. If a list of divisors were to be logarithmic in N, it needs to take less than 33 bits. I believe there is an infinite amount of ...
0
votes
1answer
90 views

Why does IP = PSPACE

Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it? I looked at many research papers but its very hard to understand the formalism unless you have a solid ...
0
votes
0answers
30 views

Is there such thing as average space complexity? If so, what is it for Timsort?

I was reading about Timsort's use in Python and wondered what the time and space complexities were which are dispalyed on the wikipedia page. The Wikipedia page lists average time complexity for ...
0
votes
1answer
64 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
2
votes
1answer
29 views

Padding in proof of space hierarchy theorems

Referring to the Wikipedia proof : Wikipedia proves the space hierarchy theorem using the following language: $$ L = \{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$...
3
votes
0answers
49 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
2
votes
1answer
63 views

Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
2
votes
1answer
44 views

$\log n$ lower bound for space complexity

I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following: Since the TM's work tapes are separated from its input tape, it makes sense ...
0
votes
1answer
71 views

Can this recursive algorithm be converted to an iterative algorithm in O(1) space?

I am trying to convert this recursive algorithm ...
0
votes
0answers
36 views

Build a Turing machine to prove that a problem is $NL$

If we the language $A$, which is defined like this: $$A = \{\langle G,s,t \rangle \} \mid \text{ There is a maximum path in graph $G$ that begin in $s$} \} $$ I want to build a Turing Machine that ...
0
votes
1answer
87 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
2
votes
1answer
43 views

Parts of a function used in Space Complexity

I'm finding contradictory information online where some places only consider auxiliary space and others define it as Space Complexity of an algorithm is total space taken by the algorithm with ...
4
votes
2answers
370 views

Should the certificate for NPSPACE be polynomial in size?

There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that ...
0
votes
2answers
100 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
1
vote
1answer
72 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
6
votes
0answers
453 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
3
votes
1answer
39 views

Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges. In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
2
votes
2answers
87 views

Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I ...
1
vote
1answer
80 views

Check array in linear time with a constant space complexity

Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false. E.g. ...
0
votes
0answers
34 views

Understanding the Space Hierarchy Theorem and its proof

This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake. The intuition behind the Space Hierarchy Theorem is that "there are Turing ...
0
votes
1answer
33 views

Space complexity of a variant of st-connectivity

Consider a variant of STCON, called 2STCON, which is defined like this: $$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$ This ...
2
votes
0answers
108 views

How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?

What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: The minimum ...
0
votes
1answer
91 views

Prove NLOGSPACE$\subset$PSPACE

Condidering the proof, NLOGSPACE$\subset$PSPACE I wrote following proof: NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\...
1
vote
0answers
35 views
0
votes
1answer
24 views

Big o notation for sublinear algorithm in streaming algorithm

Excuse me if this is obvious. At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I ...
14
votes
0answers
142 views

What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
1
vote
1answer
49 views

Randomized Version of NP

I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc. Since the above classes are well-known, I will ...
1
vote
1answer
53 views

Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over ...
0
votes
0answers
20 views

What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?

What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution? Could you, please, check my reasoning. Is it correct? Here is my algorithm for ...
1
vote
1answer
30 views

What is uniformity in Boolean circuits exactly?

I have two questions on Kaveh's answer to Definition of uniform boolean circuit : Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
1
vote
1answer
70 views

Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
1
vote
1answer
472 views

Can someone help me understand the time and space complexity?

Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the ...
0
votes
1answer
25 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
8
votes
1answer
797 views

why does LSPACE(log space) complexity class exist but not logtime?

I noticed that in complexity classes, logspace class is defined but there is no logtime. I was wondering how is that possible? Normally, I would expect the opposite, It is possible to do a search ...
1
vote
1answer
111 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
0
votes
0answers
42 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
1
vote
1answer
78 views

Indexing a huge dataset (that does not fit into central memory)

The problem. Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are ...
1
vote
0answers
59 views

Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
0
votes
0answers
13 views

Inverse VR-Vision, theoretical possibilities and the additional requirements

When using VR-Vision for looking around and the vision is from some point of interest, the look-around is a rotation from inside that point and it reqires a record of a 360° photo or a 360° camera ...
2
votes
0answers
39 views

Space-Complexity of Van Eck's Sequence

What is the space-complexity of Van Eck's sequence? https://oeis.org/A181391 Input: $x$ (number in binary representation with $n$ bits) Output: $x$th number in Van Eck's sequence Length of input: $n$ ...

1
2 3 4 5
9