Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel
  • Member for 6 years, 1 month
  • Last seen this week
  • Paris, France
27 votes
Accepted

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

26 votes
Accepted

"partial sorting" algorithms (aka "partitioning")

25 votes
Accepted

Does an algorithm's space complexity include input?

22 votes
Accepted

Is SAT an existential question?

18 votes
Accepted

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

17 votes

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

16 votes

False proofs that look correct

15 votes
Accepted

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

15 votes
Accepted

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

12 votes

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

10 votes

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

10 votes
Accepted

Correctness of FIPS 186-4 square test algorithm

10 votes
Accepted

Count number of non-contiguous occurrences in string

9 votes

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

8 votes
Accepted

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

8 votes

Arrow notation?

7 votes

Set theory pertaining to category theory and functional programming

7 votes
Accepted

Generating Isomorphic Graphs

7 votes

Length of a regular expression

6 votes
Accepted

Are reversed reverse preorder traversals equivalent to a postorder traversal?

6 votes
Accepted

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

6 votes
Accepted

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

6 votes
Accepted

Compute Permutation Number

6 votes
Accepted

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

5 votes
Accepted

Is this variant of Exact Path Length Problem easy or NP Complete

5 votes
Accepted

When converting a epsilon NFA to NFA to DFA, how to handle the start state?

5 votes
Accepted

Ordered sequence with logarithmic insert and remove

5 votes
Accepted

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

5 votes
Accepted

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

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))$?

1
2 3 4 5
15