Okay, I speak no German beyond the obligatory tourists 10; but let me see if I can help you out here. One translation of that passage you cite is:
An investigation of the interpolation search proves as very complex, as running time can however O(log(log(n))) (n is the number of elements) in the average case be accepted. In the most unfavorable (the interpolated expected position always is at the edge) case the running time amounts to however O(n).
And If I interpolate that(1): The analysis of the interpolation search is very complex. It can achieve O(log log N) in the average case, but in the worst case it can approach O(N).
By your own reference, the analysis is very complex. Do you wonder that I did not do such analysis?
All I knew at the time of my original posting, is that on a previous occasion, (8 or 10 years ago), for a similar application, I had coded a dictionary search which--by trading calculation complexity for costly IO--beat out a both a standard binary search and a modified binary search. That was real code on real data, quite possibly still running helping the belastingdienst collect duty and taxes and 21 other functions.
I had until this discussion never heard of an "interpolation search" (what a stupid name!), nor had I any idea of it's "theoretical efficiency"--nor cared to know.
So, in the absence of that knowledge, but knowing it could beat O(log N), I said: O{1} instead of "better than O(log N)". Big deal. Get over it.
As for my demo code "breaks interpolation search just after the first step!". I didn't set out to code an
"interpolation search", nor even a piece of "certified code". Just to demonstrate the possibility. Eg. a starting point not an end point. It was imperfect as posted. Once again, get over it.
This reminds me of the kids that would complain about the "offside rule having been violated" during schoolyard games of 15-or-16-per-side.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
|