A trivial algorithm whose analysis isn't

摘要

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.