Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
0
votes
0answers
44 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
33 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
42 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
265 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
1answer
23 views

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
0
votes
0answers
208 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
95 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
74 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
62 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
123 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
134 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
38 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 $...
0
votes
0answers
97 views

Convert conjunctive normal form to equivalent boolean formula with only NOR gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with ...
0
votes
0answers
91 views

Is the algorithm to solve 4SAT correct and what it's both time and space complexity?

The algorithm works as follows: For each clause, the algorithm turns the middle disjunction into conjunction, i.e. if an arbitrary clause is of the form: (l1 ∨ l2) ∨ (l3 ∨ l4) Then after ...
0
votes
0answers
61 views

Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
0
votes
0answers
64 views

Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
0
votes
0answers
315 views

What is the time and space complexity of unidirectional bfs and bidirectional bfs?

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
-1
votes
1answer
321 views

Relationship between L and PSPACE

I have a question have to answer, so that, if anyone have the answer, please help me. The problem is: Give a self-contained proof that $\mathsf{L} \neq \mathsf{PSPACE}$ where: $\qquad \mathsf{L} ...
-1
votes
1answer
173 views

What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n [closed]

Note that this is not duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is not the same. I need an algorithm that ...
-1
votes
1answer
223 views

Find the 10 top most occurring strings in a huge array of objects

Find the 10 top most occurring strings in a huge array of Strings. Since the array is huge, it is not possible to load it in memory completely. My idea is to parse the arrays one by one and put the ...
-1
votes
0answers
22 views
-2
votes
5answers
225 views

Algorithm to generate non-repeating random numbers of O(1) memory?

Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers? I can remember numbers in the hash set and it will be $O(1)$ time, but the set ...
-3
votes
1answer
91 views

Why is Mixed Quantified Horn SAT in PSPACE?

I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE? My study: To prove QSAT to be in PSPACE: ...
-3
votes
0answers
31 views

What is the space complexity of the following procedure? [duplicate]

Please help me calculate the space complexity of the following program: int Sum(int A[ ], int n) { ...