From bcd97e5735a8668aa5c49fcfde0d49ce4fc8a88a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 26 Mar 2008 18:47:10 +0100 Subject: [PATCH] Accuracy finished. --- opt.tex | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) diff --git a/opt.tex b/opt.tex index e058beb..ce1ecd6 100644 --- a/opt.tex +++ b/opt.tex @@ -284,7 +284,7 @@ has disappeared since $\(v)>r$ and therefore the desired bound is at least We will now sum the sizes of the lists over all vertices containing corrupted items. \lemma -After~$n$ items have been inserted, the heap contains at most~$n/2^{r-3}$ corrupted +After~$n$ items have been inserted, the heap contains at most~$n/2^{r-2}$ corrupted items at any given time. \proof @@ -302,20 +302,22 @@ tree of every queue in the heap. The actual trees can be much sparser, but the above claim guarantees that the total size of the master trees is bounded by the number of insertions properly. -So let us have a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices +So let us consider a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices of rank~$i$ and each such vertex contains a~list of at most~$2^{\lceil i/2\rceil - r/2}$ items by the previous lemma. Summing over all ranks greater than~$r$, we get that the total number of corrupted items in this tree is at most: $$ \sum_{i=r+1}^k 2^{k-i}\cdot 2^{\lceil i/2\rceil - r/2} -= 2^{k-r/2} \cdot \sum_i 2^{\lceil i/2\rceil - i} -\le 2^{k-r/2} \cdot \sum_i 2^{-i/2} += 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{\lceil i/2\rceil - i} +\le 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{-i/2} +\le 2^{k-r} \cdot \sum_{i=0}^\infty 2^{-i/2}. $$ - -\FIXME{Finish the proof and update the claim of the lemma.} - - +The sum of a~geometric series with quotient $2^{-1/2}$ is less than four, so the +last formula is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices, +this makes less than $n_k/2^{k-2}$ corrupted items as we asserted. \qed +\paran{Analysis of time complexity} + \endpart -- 2.39.2