From 7cb6494580b175ca7f258b2c06f84a41ba043e0b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 14:30:43 +0200 Subject: [PATCH] Minor. --- adv.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/adv.tex b/adv.tex index 3b1e7ed..fe9ad19 100644 --- a/adv.tex +++ b/adv.tex @@ -312,7 +312,7 @@ and deletions on the heap. To analyze the time complexity of this algorithm, we will use the standard theorem on~complexity of the Fibonacci heap: -\thmn{Fibonacci heaps} The~Fibonacci heap performs the following operations +\thmn{Fibonacci heaps, Fredman and Tarjan \cite{ft:fibonacci}} The~Fibonacci heap performs the following operations with the indicated amortized time complexities: \itemize\ibull \:\ (insertion of a~new element) in $\O(1)$, @@ -491,8 +491,8 @@ $$ $$ As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time there is enough space in the heap to process the whole graph. So~there are -at most~$\beta(m,n)$ phases and we already know (Lemma~\ref{ijphase}) that each -phase runs in linear time. +at most~$\beta(m,n)$ phases and we already know that each phase runs in linear +time (Lemma~\ref{ijphase}). \qed \cor -- 2.39.2