The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
RAIRO. Informatique théorique, Tome 17 (1983) no. 4, pp. 365-385. 
@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. Informatique th\'eorique},
     pages = {365--385},
     publisher = {EDP-Sciences},
     volume = {17},
     number = {4},
     year = {1983},
     mrnumber = {743895},
     zbl = {0523.68031},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1983__17_4_365_0/}
}
TY  - JOUR
AU  - Louchard, G.
TI  - The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
JO  - RAIRO. Informatique théorique
PY  - 1983
SP  - 365
EP  - 385
VL  - 17
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1983__17_4_365_0/
LA  - en
ID  - ITA_1983__17_4_365_0
ER  - 
%0 Journal Article
%A Louchard, G.
%T The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
%J RAIRO. Informatique théorique
%D 1983
%P 365-385
%V 17
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1983__17_4_365_0/
%G en
%F ITA_1983__17_4_365_0
Louchard, G. The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation. RAIRO. Informatique théorique, Tome 17 (1983) no. 4, pp. 365-385. http://archive.numdam.org/item/ITA_1983__17_4_365_0/

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

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 | Zbl

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

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 | Zbl

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

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

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 | Zbl

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

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

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 | Zbl

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 | Zbl

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

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.