User Nathaniel

27 votes

Accepted

Is there an algorithm whose time complexity is between polynomial time and exponential time？

answered Dec 22, 2021 at 14:12

26 votes

Accepted

"partial sorting" algorithms (aka "partitioning")

answered Apr 5, 2022 at 23:51

22 votes

Accepted

Is SAT an existential question?

answered Oct 16, 2022 at 16:31

22 votes

Accepted

Does an algorithm's space complexity include input?

answered Jan 19 at 13:52

18 votes

Accepted

Why is proving something is NP-complete useful, and where can I use it?

answered Nov 1, 2022 at 14:59

17 votes

Can anyone give me an instance of 3SAT with exactly one solution?

answered Feb 18, 2021 at 14:37

15 votes

Accepted

What are you allowed to move into the big O notation for it to be still correct?

answered Nov 21, 2021 at 14:11

15 votes

Accepted

Can we transfer every DFA to DFAs with start state having no in edge?

answered Mar 11 at 12:01

12 votes

How to find the largest power of two divisor of a given integer?

answered Apr 5, 2021 at 12:15

10 votes

Algorithm to get any spanning tree not necessarily a minimum spanning tree

answered Apr 5, 2021 at 14:04

10 votes

Accepted

Correctness of FIPS 186-4 square test algorithm

answered Jan 15 at 12:50

10 votes

Accepted

Count number of non-contiguous occurrences in string

answered Nov 21, 2022 at 20:52

9 votes

Prove that every substring closed language L ⊆ {0, 1}* is regular

answered Feb 20, 2022 at 15:57

8 votes

Accepted

What is a witness string? I unable to understand the concept

answered Mar 4, 2022 at 10:31

8 votes

Arrow notation?

answered Feb 21, 2021 at 20:23

7 votes

Set theory pertaining to category theory and functional programming

answered May 14, 2021 at 14:18

7 votes

Accepted

Generating Isomorphic Graphs

answered Dec 23, 2021 at 0:08

7 votes

Length of a regular expression

answered May 17, 2022 at 18:59

6 votes

Accepted

Are reversed reverse preorder traversals equivalent to a postorder traversal?

answered May 19, 2022 at 3:43

6 votes

Accepted

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

answered Apr 23, 2022 at 9:57

6 votes

Accepted

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

answered Apr 10, 2022 at 23:53

6 votes

Accepted

Compute Permutation Number

answered Nov 24, 2022 at 18:28

6 votes

Accepted

What is the difference between the set containing the empty string and the set containing nothing at all?

answered Jan 10 at 14:12

5 votes

Accepted

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

answered Apr 22, 2022 at 22:52

5 votes

Accepted

Doubt about computing running time / time complexity of a function in Python

answered Apr 9, 2022 at 22:09

5 votes

Accepted

$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

answered Mar 13, 2022 at 17:41

5 votes

Accepted

n! and 2^(n^2); which one grows faster

answered Jan 25, 2022 at 21:17

5 votes

Equivalence relation between two CFG's

answered Nov 22, 2021 at 18:59

5 votes

An α-good tree with n nodes has height O(log n)

answered May 11, 2022 at 21:07

5 votes

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

answered May 17, 2022 at 22:50

Stack Exchange Network

423 Answers

Is there an algorithm whose time complexity is between polynomial time and exponential time？

"partial sorting" algorithms (aka "partitioning")

Is SAT an existential question?

Does an algorithm's space complexity include input?

Why is proving something is NP-complete useful, and where can I use it?

Can anyone give me an instance of 3SAT with exactly one solution?

What are you allowed to move into the big O notation for it to be still correct?

Can we transfer every DFA to DFAs with start state having no in edge?

How to find the largest power of two divisor of a given integer?

Algorithm to get any spanning tree not necessarily a minimum spanning tree

Correctness of FIPS 186-4 square test algorithm

Count number of non-contiguous occurrences in string

Prove that every substring closed language L ⊆ {0, 1}* is regular

What is a witness string? I unable to understand the concept

Arrow notation?

Set theory pertaining to category theory and functional programming

Generating Isomorphic Graphs

Length of a regular expression

Are reversed reverse preorder traversals equivalent to a postorder traversal?

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Compute Permutation Number

What is the difference between the set containing the empty string and the set containing nothing at all?

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Doubt about computing running time / time complexity of a function in Python

$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

n! and 2^(n^2); which one grows faster

Equivalence relation between two CFG's

An α-good tree with n nodes has height O(log n)

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?