Skip to main content

New answers tagged

2 votes
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 ...
Emil Jeřábek's user avatar
3 votes

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 ...
Pseudonym's user avatar
  • 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.
Ellen Spertus's user avatar
0 votes

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 ...
D.W.'s user avatar
  • 162k
5 votes

Complexity of ExpTime VS Pspace

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 ...
D.W.'s user avatar
  • 162k
0 votes

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

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: ...
codeR's user avatar
  • 1,467

Top 50 recent answers are included