The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
Louchard, G.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983), p. 365-385 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1983__17_4_365_0,
     author = {Louchard, G.},
     title = {The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {17},
     year = {1983},
     pages = {365-385},
     mrnumber = {743895},
     zbl = {0523.68031},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1983__17_4_365_0}
}

Louchard, G. The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 17 (1983) pp. 365-385. http://gdmltest.u-ga.fr/item/ITA_1983__17_4_365_0/

1. H. Bateman, Higher Transcendal Functions, Vol. 1, McGraw-Hill, 1953. | MR 58756

2. F. W. Burton and G. N. Lewis, A Robust Variation of Interpolation Search, Information Processing Letters, Vol. 10, No. 4 and 5, 1980, pp.198-201.

3. S. Chandrasekhar, Stochastic Problems in Physics and Astronomy, Review of Modern Physics, Vol. 15, 1943, pp. 57-59. | MR 8130 | Zbl 0061.46403

4. D. R. Cox and H. D. Miller, The Theory of Stochastic Processes, Chapman and Hall, 1980. | Zbl 0359.60004

5. M. D. Donsker, Justification and Extension of Doob's Heuristic Approach to the Kolmogorov-Smirnov Theorems, Annals of Mathematical Statistics, 1952, pp. 277-281. | MR 47288 | Zbl 0046.35103

6. J. L. Doob, Heuristic Approach to the Kolmogorov-Smirnov Theorems, Annals of Mathematical and Statistics, Vol. 20, 1949, pp. 393-403. | MR 30732 | Zbl 0035.08901

7. P. Flajolet, Analyse d'algorithmes de manipulation d'arbres et de fichiers, Cahiers du BURO, 1981, pp. 34-35.

8. G. H. Gonnet, Interpolation and Interpolation-Hash Searching, Research Report CS-77-02, University of Waterloo, 1977. | MR 2716070

9. G. H. Gonnet, D. R. Lawrence and J. A. George, An Algorithmic and Complexity Analysis of Interpolation Search, Acta Informatica, Vol. 13, 1980, pp. 39-52. | MR 557548 | Zbl 0405.68057

10. K. Ito and Jr. H. P. Mckean, Diffusion Processes and their Sample Paths, Springer-Verlag, 1974. | MR 345224 | Zbl 0285.60063

11. D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973. | MR 445948 | Zbl 0302.68010

12. G. N. Lewis, N. J. Boynton and F. W. Burton, Expected Complexity of Fast Search with Uniformly Distributed Data, Information Processing Letters, Vol. 13, No. 1, 1981, pp. 4-7. | MR 636310 | Zbl 0468.68061

13. Y. Perl, A. Itai and H. Avni, Interpolation Search. A Log Log N Search, Communications of the ACM, Vol. 21, No. 7, 1978, pp. 550-553. | MR 489109 | Zbl 0378.68029

14. R. Sedgewick, Mathematical Analysis of Combinatorial Algorithms in Probability and Computer Science, G. LATOUCHE and G. LOUCHARD, Ed., Academic Press (to appear). | MR 753477

15. A. C. Yao and F. F. Yao, The Complexity of Searching an Ordered Random Table, Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976, pp. 173-177.