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/

[1] Barvinok A., Fomin S., Adv. in Appl. Math., 18:3 (1997), 271–285 | DOI | MR | Zbl

[2] Bernstein D., The computational complexity of rules for the character table of $S_n$, arXiv.org: math/0309225 | MR

[3] Ivanov V., Olshanski G., Symmetric Functions 2001: Surveys of Developments and Perspectives, Proc. NATO Advanced Study Institute, ed. S. Fomin, Kluwer, 2002, 93–152 | DOI | MR

[4] Knut D., Iskusstvo programmirovaniya dlya EVM. T. 3. Sortirovka i poisk, Mir, M., 1978 | MR | Zbl

[5] Vershik A. M., Kerov S. V., DAN SSSR, 233:6 (1977), 1024–1027 | MR | Zbl

[6] Vershik A. M., Kerov S. V., Funkts. analiz i ego pril., 19:1 (1985), 25–38 | MR

[7] Logan B. F., Shepp L. A., Adv. Math., 26:2 (1977), 206–222 | DOI | MR | Zbl

[8] Stanley R. P., Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999 | MR

[9] Stembridge J. R., Interaction of Combinatorics and Representation Theory,, MSJ Memoirs, 11, Math. Soc. Japan, Tokyo, 2001, 1–38 | MR | Zbl