A Trivial Algorithm Whose Analysis isn't.
Abstract
Very few theoretical results have been obtained to date about the behavior of information retrieval algorithms under random deletions, as well as random insertions. The present paper offers a possible explanation for this dearth of results, by showing that one of the simplest such algorithms already requires a surprisingly intricate analysis. Even when the data structure never contains more than three items at a time, it is shown that the performance of the standard tree search/insertion/deletion algorithm involves Bessel functions and the solution of bivariate integral equations. A step-by-step expository analysis of this problem is given, and it is shown how the difficulties arise and can be surmounted. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1977
- Accession Number
- ADA040486
Entities
People
- Arne T. Jonassen
- Donald Knuth
Organizations
- Stanford University