Editing Interpolation search (section)

==Performance==

Using [[big-O notation]], the performance of the interpolation algorithm on a data set of size ''n'' is ''O''(''n''); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be ''O''(log log ''n'').<ref>Weiss, Mark Allen (2006). ''Data structures and problem solving using Java'', Pearson Addison Wesley</ref><ref>Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.</ref><ref>Sedgewick, Robert (1990), ''Algorithms in C'',  Addison-Wesley</ref>

Dynamic interpolation search extends the ''o''(log log ''n'') bound to other distributions and also supports ''O''(log ''n'') insertion and deletion.<ref name="b050">{{cite journal | last=Mehlhorn | first=Kurt | last2=Tsakalidis | first2=Athanasios | title=Dynamic interpolation search | journal=Journal of the ACM | volume=40 | issue=3 | date=1993 | issn=0004-5411 | doi=10.1145/174130.174139 | pages=621–634}}</ref><ref name="x493">{{cite book | last=Andersson | first=Arne | last2=Mattsson | first2=Christer | title=Automata, Languages and Programming | chapter=Dynamic interpolation search in o(log log n) time | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | volume=700 | date=1993 | isbn=978-3-540-56939-8 | doi=10.1007/3-540-56939-1_58 | page=15–27}}</ref>

Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.  It can be useful for locating a record in a large sorted file on disk, where each probe involves a disk seek and is much slower than the interpolation arithmetic.

Index structures like [[B-tree]]s also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated [[Online algorithm|online]].  Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on-disk datasets.