# Tag Info

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