# Tag Info

### Is Goedel's 1st theorem not algorithmically derivable?

Your reasoning is incorrect. It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the ...
• 7,754

### Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

An alternative solution still using domain transformation/change of variables. $$T(n) = T(\sqrt{n}) + \log \log n$$ 1. Let $m = \log n$ We can then define a new function $S$ based on how $m$ ...
• 4,381
Accepted

### Every AVL tree may be red black tree

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule: Every path from a given node to any of its descendant NIL nodes contains the ...
• 271k

• 271k
Accepted

### If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?

Here is a simple counterexample: \begin{align*} &f(2m) = 2^{2^{4m}} & &g(2m) = 2^{2^{4m+1}} \\ &f(2m+1) = 2^{2^{4m+3}} & &g(2m+1) = 2^{2^{4m+2}} \end{align*} The first ...
• 271k
Accepted

### Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

In this context, lexicographic order means: First order by length. Within each length, order lexicographically. You're saying that the proof is incorrect, but in fact it is only inaccurate in that ...
• 271k

### Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?

It's a proof by contradiction that could easily be rewritten as a direct proof. To rephrase it as a direct proof, we divide it into two claims: $max$ is an element of $A$. $max \geq A[j]$ for all $j$...
• 271k

### Number of possible heaps on $\{1,...,2^h-1\}$

The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$. Instead of looking at ...
• 7,534

### how to prove that log(n!) >= c n log(n) for some c >0?

$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$ so $\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$
Accepted

### $\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again. To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", &...
• 35.3k

### Not understanding this way of proving undecidability of the termination problem

This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain ...
• 16.5k
Accepted

### Disprove: if L is decidable then Prefix(L) is decidable

It is correct that if $L$ is decidable language $\text{Prefix}(L)$ can be undecidable. The language $L$ given in the question is a concise example of a decidable language the prefix language of which ...
• 35.3k