Re: [PATCH 1/3] Lazily open pack index files on demand

From: Karl Hasselström <kha@treskal.com>
Date: May 28, 2007, 17:40 UTC
Message-ID: <20070528174037.GA1118@diana.vm.bytemark.co.uk>
In-Reply-To: <alpine.LFD.0.98.0705280907290.26602@woody.linux-foundation.org>

On 2007-05-28 09:22:02 -0700, Linus Torvalds wrote:

Show 5 quoted lines

> Secondly, the cost of Newton isn't "almost O(1)". I don't know
> _what_ it is (the rule of thumb with Newton-Raphson should be that
> the number of significant correct digits in the answer doubles with
> each iteration: I think that probably means that it should
> approximate O(loglog(n)), but I haven't thought deeply about it.

With binary search, the number of correct bits in the index increases by 1 for each iteration. With Newton iteration, the number of correct bits doubles for each iteration. So the number of Newton iteration should be the log of the number of binary search iterations, i.e. log log n like you say.

But for non-astronomical values of n, I agree that this kind of big-O analysis is much inferior to benchmarking.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle