From d2cecf1bf3e7eb17dd1f6fb6490a2e23413c3cbf Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 3 May 2008 20:41:01 +0200 Subject: [PATCH] More corrections to Appendix A. --- notation.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/notation.tex b/notation.tex index 81efb49..cc44d4a 100644 --- a/notation.tex +++ b/notation.tex @@ -165,7 +165,7 @@ introduced by Ackermann \cite{ackermann:function} in the context of computability theory. Its original purpose was to demonstrate that not every recursive function is also primitive recursive. At the first sight, it does not seem related to efficient algorithms at all. Its various inverses however occur in -analyses of various algorithms and mathematical structures surprisingly often: +analyses of algorithms and mathematical structures surprisingly often: We meet them in Section \ref{classalg} in the time complexity of the Disjoint Set Union data structure and also in the best known upper bound on the decision tree complexity of minimum spanning trees in Section \ref{optalgsect}. Another @@ -174,7 +174,7 @@ Klazar's survey \cite{klazar:gdss}), but as far as we know, these are not otherw related to the topic of our study. Various sources differ in the exact definition of both the Ackermann's -function and its inverse, but most of the differences are in factors that +function and its inverse, but most of these differences are in factors that are negligible in the light of the giant asymptotic growth of the function.\foot{% To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity, Ackermann's function is rarely defined the same way twice. We would not presume to buck -- 2.39.2