# Tag Info

Accepted

### Proof that $ALL_{DFA} \in SPACE(log^{2}n)$

By the characterization that you noted, the complement of $\mathrm{ALL_{DFA}}$ is in $\mathrm{NL=NSPACE}(\log n)$ because directed $s$-$t$-connectivity is in $\mathrm{NL}$. Then apply Savitch’s ...
• 1,341

### Do edge lists have O(E) storage if default values are used for absent keys?

Just as an initial comment, it's not entirely settled what Bachmann big-oh notation formally means when you have more than one variable. There are multiple competing definitions. But let's leave that ...
• 22.3k
1 vote
Accepted

### What is the complexity of this tree recursive integer replacement algorithm?

I figured out the answer to my question. The time complexity is $O(\log(n))$ because $n$ is halved every two calls (worst case). For more detail, see my solution.
• 1,568

### Is there a lower bound on space complexity of non-in-place sorting?

You might be interested in external sorting, which can be viewed as loosely related to the study of sorting algorithms where the space complexity is much less than $O(n)$. In particular, we assume ...
• 162k
No one knows. While it is conjectured that PSPACE $\ne$ EXPTIME, no one has any proof. In other words, it is consistent with all of our state of knowledge that PSPACE = EXPTIME. In particular: If ...
Here, you can get away with branching in only one direction greedily. Thus, you can even convert the recursion into a simple while loop, which takes about $O(\log n)$ steps. Here is the code: ...