ICS Theory Group

ICS 269, Winter 2004: Theory Seminar


5 Mar 2004:
What of the input can we explore besides n?
Jonathan Z. Sun

In "Interploation search for non-independent data" by Demaine, Jones and Patrascu [SODA 2004, pp.522-523], the complexity of a simple searching algorithm is analyzed not by the input size n but by a gap ratio Delta = (max distance of two adjacent values)/(min distance of two adjacent values). Previous work on interpolation search always assumed some distribution on the input data and (still) used the input size n for complexity analysis.

Time allowing, there will be a discussion of "A note on the nearest neighbor in growth-restricted metrics" by Hildrum, Kubiatowicz, and Rao [SODA 2004, pp.553-554]. In this paper, although the complexity is represented by the input size n, it is based on a constraint of the input.