From dbe915aea3c8d424f8bdca570f59bb50ac5b44b1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 3 Feb 2008 21:19:21 +0100 Subject: [PATCH] Fix definition of \beta and \log^*. --- adv.tex | 2 +- notation.tex | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/adv.tex b/adv.tex index 155bd98..400b8a0 100644 --- a/adv.tex +++ b/adv.tex @@ -376,7 +376,7 @@ how the algorithm could have stopped growing the tree~$R_i^j$: \thm\id{itjarthm}% The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time -$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n < m/n \}$. +$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$. \proof Phases are finite and in every phase at least one edge is contracted, so the outer diff --git a/notation.tex b/notation.tex index 80ebe3f..5517660 100644 --- a/notation.tex +++ b/notation.tex @@ -39,8 +39,8 @@ \n{$\log n$}{a binary logarithm of the number~$n$} \n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$} \n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$} -\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$} -\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]} +\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$} +\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n \le m/n \}$ \[itjarthm]} \n{$W$}{word size of the RAM \[wordsize]} \n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]} \n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]} -- 2.39.2