4

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$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=...


3

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


2

... further simplify $(n/2)\log(n/2)$ --> $(n/2)\log(n^{-2})$, ... This is wrong. In fact, for $n\ge 3$, $n^{\log_3 2}\ge 2$, so \begin{align} (n/2)\log(n/2)&=(n/2)(\log n-\log2)\\ &\ge (n/2)\cdot\left(1-\log_3 2\right)\log n\\ &=\left(1-\log_3 2\right)/2\cdot n\cdot \log n, \end{align} and $\log(n!)\ge \left(1-\log_3 2\right)/2\cdot n\cdot \...


2

Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\...


2

It seems that $\dagger\dagger$ is consistent with $\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n < 140$ (i.e., the line marked with $\ddagger$). Then, for any $n \in \{1, \dots, 139\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.


1

I would suggest the following $O(n)$ approach using a monotone stack which is nothing but a regular stack but also satisifes the invariant that its elements are in monotone order. Say you want to make a strictly monotone stack $S$ which is increasing viewed from the last in to the first out: you would process elements $x$ in order with the following policy: ...


1

Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation: $\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$. Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$. Claim 1. $\epsilon(S) \supseteq S$....


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