Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
David Faux's user avatar
David Faux's user avatar
David Faux's user avatar
David Faux
  • Member for 11 years, 8 months
  • Last seen more than a month ago
  • United States
31 votes
2 answers
31k views

Why is push_back in C++ vectors constant amortized?

22 votes
3 answers
11k views

If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

9 votes
1 answer
29k views

Why is the clique problem NP-complete? [duplicate]

8 votes
3 answers
4k views

Why is $3^n = 2^{O(n)}$ true?

8 votes
2 answers
4k views

How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

6 votes
2 answers
1k views

Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions?

6 votes
1 answer
2k views

Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?

5 votes
1 answer
1k views

How is verifying whether an assignment satisfies a boolean formula possible in polynomial time?

5 votes
3 answers
390 views

Why is $(\log(n))^{99} = o(n^{\frac{1}{99}})$

4 votes
4 answers
8k views

Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

4 votes
1 answer
202 views

Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?

3 votes
1 answer
1k views

Why is the Shannon entropy 0.94 in this example?

3 votes
3 answers
10k views

How does one make an unambiguous context-free grammar for arithmetic expressions?

3 votes
1 answer
202 views

Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

3 votes
1 answer
1k views

How can repeated addition/multiplication be done in polynomial time?

3 votes
2 answers
8k views

What do these arrows in design pattern diagrams mean?

3 votes
1 answer
2k views

How does sorting come into play with convex hull?

2 votes
1 answer
73 views

How does this algorithm for verifying if a string is $0^n1^n$ work?

2 votes
2 answers
140 views

How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

2 votes
1 answer
1k views

Where do these DRAM row/column calculations come from?

2 votes
1 answer
98 views

Does $O(1) * o(1)$ equal a $o(1)$ function?

2 votes
1 answer
14k views

How do I compute the luminance of a pixel?

2 votes
3 answers
952 views

When does $1.00001^n$ exceed $n^{100001}$?

2 votes
1 answer
4k views

How can I quantify the number of swaps required for insertion sort?

1 vote
1 answer
94 views

For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

1 vote
3 answers
6k views

Why is the node with the greatest DFS post-order number not necessarily a sink?

1 vote
1 answer
3k views

How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

1 vote
1 answer
6k views

Are Turing-recognizable languages closed under intersection?

0 votes
1 answer
96 views

Finding $c$ and $n_0$ for a big-O bound