# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

319 questions
Filter by
Sorted by
Tagged with
1answer
1k views

### Prove the following problem is NL-complete

Suppose A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{$$G$$ undirected}, \\ \text{$$s$$ and $$t$$ are nodes in $$G$$}, \\ \text{there is a path of length $$d$$ from \(...
1answer
317 views

### Show that k-clique lies in L

The following exercise is difficult for me: Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$. Hint: A $k$-clique denotes $k$ ...
2answers
196 views

### Show that the multiplication lies in FL

I don't know exactly how to solve the exercise below. Show that the multiplication lies in $\text{FL}$. Hint: A useful approach to a solution is to split the exercise into two parts and to ...
1answer
477 views

### Showing that Independent set of size $k$ can be decided using logarithmic space

An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of ...
2answers
946 views

### Time complexity for count-change procedure in SICP

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
1answer
995 views

### Relation between interactive proof systems (IP), NP, coNP, PSPACE

I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest ...
1answer
540 views

2answers
512 views

### Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
1answer
632 views

### Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
2answers
2k views

### What's the complexity of Spearman's rank correlation coefficient computation?

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
2answers
413 views

### Time-space tradeoff for missing element problem

Here is a well-known problem. Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array. The problem can be solved in $O(n)$ space and time: read the ...
1answer
128 views

### Complexity of space density and sequentiality

I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms. When we measure algorithms we tend to give the big-Oh notation ...
1answer
1k views

### Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1

I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak: [Q 4.1] Prove the existence of a universal TM for space bounded computation (...
2answers
624 views

### Complete Problems for $DSPACE(\log(n)^k)$

We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy? To be ...
2answers
708 views

### Expected space consumption of skip lists

What is the expected space used by the skip list after inserting $n$ elements? I expect that in the worst case the space consumption may grow indeﬁnitely. Wikipedia says space $O(n)$. How can this ...
1answer
493 views

### Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore \$st\text{-}non\...
3answers
2k views

### The space complexity of recognising Watson-Crick palindromes

I have the following algorithmic problem: Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes. Watson-Crick palindromes are strings whose reversed ...