The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation

G. Louchard

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1983)

  • Volume: 17, Issue: 4, page 365-385
  • ISSN: 0988-3754

How to cite

top

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 17.4 (1983): 365-385. <http://eudml.org/doc/92194>.

@article{Louchard1983,
author = {Louchard, G.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {analysis of sorted tables; Brownian motion; complexity of manipulation algorithms; probabilistic behaviour},
language = {eng},
number = {4},
pages = {365-385},
publisher = {EDP-Sciences},
title = {The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation},
url = {http://eudml.org/doc/92194},
volume = {17},
year = {1983},
}

TY - JOUR
AU - Louchard, G.
TI - The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1983
PB - EDP-Sciences
VL - 17
IS - 4
SP - 365
EP - 385
LA - eng
KW - analysis of sorted tables; Brownian motion; complexity of manipulation algorithms; probabilistic behaviour
UR - http://eudml.org/doc/92194
ER -

References

top
  1. 1. H. BATEMAN, Higher Transcendal Functions, Vol. 1, McGraw-Hill, 1953. MR58756
  2. 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. 3. S. CHANDRASEKHAR, Stochastic Problems in Physics and Astronomy, Review of Modern Physics, Vol. 15, 1943, pp. 57-59. Zbl0061.46403MR8130
  4. 4. D. R. COX and H. D. MILLER, The Theory of Stochastic Processes, Chapman and Hall, 1980. Zbl0359.60004
  5. 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. Zbl0046.35103MR47288
  6. 6. J. L. DOOB, Heuristic Approach to the Kolmogorov-Smirnov Theorems, Annals of Mathematical and Statistics, Vol. 20, 1949, pp. 393-403. Zbl0035.08901MR30732
  7. 7. P. FLAJOLET, Analyse d'algorithmes de manipulation d'arbres et de fichiers, Cahiers du BURO, 1981, pp. 34-35. 
  8. 8. G. H. GONNET, Interpolation and Interpolation-Hash Searching, Research Report CS-77-02, University of Waterloo, 1977. MR2716070
  9. 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. Zbl0405.68057MR557548
  10. 10. K. ITO and Jr. H. P. MCKEAN, Diffusion Processes and their Sample Paths, Springer-Verlag, 1974. Zbl0285.60063MR345224
  11. 11. D. E. KNUTH, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973. Zbl0302.68010MR445948
  12. 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. Zbl0468.68061MR636310
  13. 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. Zbl0378.68029MR489109
  14. 14. R. SEDGEWICK, Mathematical Analysis of Combinatorial Algorithms in Probability and Computer Science, G. LATOUCHE and G. LOUCHARD, Ed., Academic Press (to appear). MR753477
  15. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.