Geodesic
The Number of Steps in the Robinson--Schensted Algorithm
Funkcionalʹnyj analiz i ego priloženiâ, Tome 39 (2005) no. 2, pp. 82-86

Voir la notice de l'article provenant de la source Math-Net.Ru

Suppose that a permutation $\sigma\in \mathcal{S}_n$ is chosen at random ($n$ is large) and the Robinson–Schensted algorithm is applied to compute the associated Young diagram. Then for almost all permutations the number of bumping operations performed by the algorithm is about $(128/27\pi^2)n^{3/2}$, and the number of comparison operations is about $(64/27\pi^2) n^{3/2}\log_2 n$.
Keywords: Robinson–Schensted algorithm, analysis of algorithms, Plancherel measure.
Mots-clés : Young tableaux 
@article{FAA_2005_39_2_a9,
     author = {D. Romik},
     title = {The {Number} of {Steps} in the {Robinson--Schensted} {Algorithm}},
     journal = {Funkcionalʹnyj analiz i ego prilo\v{z}eni\^a},
     pages = {82--86},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FAA_2005_39_2_a9/}
}
TY  - JOUR
AU  - D. Romik
TI  - The Number of Steps in the Robinson--Schensted Algorithm
JO  - Funkcionalʹnyj analiz i ego priloženiâ
PY  - 2005
SP  - 82
EP  - 86
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FAA_2005_39_2_a9/
LA  - ru
ID  - FAA_2005_39_2_a9
ER  - 
%0 Journal Article
%A D. Romik
%T The Number of Steps in the Robinson--Schensted Algorithm
%J Funkcionalʹnyj analiz i ego priloženiâ
%D 2005
%P 82-86
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FAA_2005_39_2_a9/
%G ru
%F FAA_2005_39_2_a9
D. Romik. The Number of Steps in the Robinson--Schensted Algorithm. Funkcionalʹnyj analiz i ego priloženiâ, Tome 39 (2005) no. 2, pp. 82-86. http://geodesic.mathdoc.fr/item/FAA_2005_39_2_a9/