21

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an algorithm could be used to solve the halting problem (assuming you knew a constant $c>0$ such that the running time is at least $c\mathit{BB}(n)$), since you ...


5

The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows: $$ \binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k $$ Where the equality $\sum_{i=0}^{k} \binom{k}{i} = 2^k$ follows from the fact that the summation on the left is counting the number of possible subsets of a set with $k$ elements, grouped by ...


4

The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general: Deciding ...


2

Backward substitution is a specific method to solve a particular problem: a linear system of equations; Backtracking is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial ...


2

There are well known inequalities: $$\frac{n^k}{k^k}\leqslant \binom{n}{k}\leqslant \frac{n^k}{k!}$$


2

"since $T(n)=O(n)$ then $T(n)=an+b$" it's wrong assumption, because big-$O$ gives only upper bound. For example $n^\alpha \in O(n)$ for $\alpha \in (0,1))$, $\log n \in O(n)$ etc., so you cannot reduce situation for only linear functions. For exact estimation you need to elaborate $O(n)$ in recurrence relation.


Only top voted, non community-wiki answers of a minimum length are eligible