# 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.