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). However, Dynamic Interpolation Search is possible in o(log log n) time using a novel data structure.
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-trees 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. Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on-disk datasets.
Read more about this topic: Interpolation Search
Famous quotes containing the word performance:
“When a book, any sort of book, reaches a certain intensity of artistic performance it becomes literature. That intensity may be a matter of style, situation, character, emotional tone, or idea, or half a dozen other things. It may also be a perfection of control over the movement of a story similar to the control a great pitcher has over the ball.”
—Raymond Chandler (1888–1959)
“What avails it that you are a Christian, if you are not purer than the heathen, if you deny yourself no more, if you are not more religious? I know of many systems of religion esteemed heathenish whose precepts fill the reader with shame, and provoke him to new endeavors, though it be to the performance of rites merely.”
—Henry David Thoreau (1817–1862)
“No performance is worth loss of geniality. ‘Tis a cruel price we pay for certain fancy goods called fine arts and philosophy.”
—Ralph Waldo Emerson (1803–1882)