For match-seeking binary search Knuth's classical figure of merit for an ordered table of n elements is
M(n) = 2[(n + 1)q + 2e] – n in which q = floor[log2(n + 1)] and e = n - (2**q - 1). Here q = 11, e = 3500 - 2047 = 1453, and thus M(3500) = 2[3501 x 11 + 2 x 1453] - 3500 = 78324 For linear search of an ORDERED table, Knuth again, the best scheme seeks 1) a glb on the search argument in the table and then 2) tests it for a match. This scheme has L(n) = 2n[(n + 1)/2 + 3n = n(n + 4) Thus L(3500) = 3500 x 3504 = 12264000 Then L(3500)/M(3500) = 12264000/78324 = 156.58. Predictably, the logarithmic-time binary-search scheme is much better, 156 times better here, than the polynomial-time linear-search one for non-trivial n. If you are going to search this table at all frequently, the case for using binary search is compelling; if not, maybe not. John Gilmore, Ashland, MA 01721 - USA
