2009-07-30 – More on O(log(log(n))) searching

Thanks to everyone for the informative comments on my previous post.

I found a bug in my simulation code which meant that many of the tests were performed on arrays that were half-full of zeroes (oops). This distorted the stats a little, and more for larger N because I tested fewer different arrays for large N. This bug caused the increase in s.d. for large N: the corrected code has the same s.d. for all N. Another effect was to increase the maximum number of iterations required to find an entry. After the fix the maximum number of iterations goes down to log(log(N))+12 for the pure secant method, and (log(N)+14)/2 for Junio's mixed secant/bisection method. Altogether much more well-behaved.

⇐ 2009-07-28 ⇐ Searching a sorted array faster than O(log(N)) ⇐ ⇒ Sainsbury's self-checkout fail ⇒ 2009-08-10 ⇒