The Number of Steps in the Robinson–Schensted Algorithm

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$.