On 2007-05-28 09:22:02 -0700, Linus Torvalds wrote:
> 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@xxxxxxxxxxx
www.treskal.com/kalle
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
