More verification.

[saga.git] / ram.tex

diff --git a/ram.tex b/ram.tex
index 7cdf752c3c919d6aa55fe1cea71513fea5060ed0..d39d9ba73f727dcafe19cb5c368457090c72c09f 100644 (file)
--- a/ram.tex
+++ b/ram.tex
@@ -307,6 +307,7 @@ scanning all~$n$ buckets takes $\O(n+m)$ time.
 %--------------------------------------------------------------------------------
 
 \section{Data structures on the RAM}
+\id{ramdssect}
 
 There is a~lot of data structures designed specifically for the RAM, taking
 advantage of both indexing and arithmetics. In many cases, they surpass the known
@@ -676,8 +677,8 @@ to precompute a~table of the values of~$f$ for all arguments whose size is $\O(k
 
 \proof
 There are $2^{\O(k^3)}$ possible combinations of arguments of the given size and for each of
-them we spend $\O(k^c)$ time by calculating the function (for some~$c\ge 1$). It remains
-to observe that $2^{\O(k^3)}\cdot \O(k^c) = \O(2^{k^4})$.
+them we spend $\poly(k)$ time on calculating the function. It remains
+to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$.
 \qed
 
 \para
@@ -798,7 +799,9 @@ us call this bit~$g_i$. This implies that the values $x_1,\ldots,x_i$
 must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
 right subtree. Both subtrees can be then constructed recursively.\foot{This
 construction is also known as the \df{cartesian tree} for the sequence
-$g_1,\ldots,g_n$.}
+$g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
+built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
+and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
 \qed
 
 \para
@@ -806,7 +809,7 @@ Unfortunately, the vector of the $g_i$'s is also too long (is has $k\log W$ bits
 and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even
 further:
 
-\nota
+\nota\id{qhnota}%
 \itemize\ibull
 \:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array,
 \:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping