Special cases.

[saga.git] / ram.tex

diff --git a/ram.tex b/ram.tex
index 824382ef6e0bcc619677bb4b6d96ec6ae13e6fd8..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