# Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $$O(n^2)$$ running time, for constructing such a standard Young's Tableaux.

But, since every permutation has a unique Young's tableau, there seems no reason as to why it cannot be done in $$O(n \log n)$$ time, which is the optimal time to identify a permutation.

Are there any known non-trivial $$\textbf{lower bounds or upper bounds}$$ for this?

Any assistance/guidance towards any of the questions is much appreciated. Thanks in advance

Sample input permutation

5,7,2,3,4,1,6

Output Young's Tableaux

1,3,4,6
2,7
5

• I suggest editing the question to incorporate that information, so the question stands on its own. We want questions to be self-contained, so people don't need to read the comments to understand what you are asking. Also, it sounds like the correspondence is to pairs of Young tableaux, not to a single tableux; if that is correct, please make the corresponding change as well. Thank you!
– D.W.
Feb 8, 2017 at 4:02
• @D.W:- No Sir, i do not need pair of Young tableaux, just a single tableaux. For eg. the tableaux on page en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence Corresponds to the permutation 8,3,1,5,2,4,7
– Vk1
Feb 8, 2017 at 4:09
• I think you need to specify the desired output more precisely. When you say that every permutation corresponds to a unique Young's tableaux, what correspondence do you have in mind? The correspondence listed on Wikipedia is between a permutation and a pair of standard Young's tableaux (not between a permutation and a single Young's tableaux). Perhaps given a permutation, you want the first of the pair of tableaux that correspond to it?
– D.W.
Feb 8, 2017 at 4:22
• @D.W. :- I have made the changes, and given an example in the description. I hope this clarifies everything.
– Vk1
Feb 8, 2017 at 13:16

## 1 Answer

I believe that no faster algorithm is known, at least if you are interested in computing both tableaux. Dan Romik shows in his paper The Number of Steps in the Robinson-Schensted Algorithm that on almost all permutations, the computational complexity is actually only $$\Theta(n^{3/2} \log n)$$. Duzhin, Kuzmin and Vasilliev show in their work RSK bumping trees and a fast RSK algorithm how to speed up the algorithm in practice by a significant constant factor. This is all I could find on the topic.

• I would hug you, if you were besides me right now. How did you know all this? You have no idea how much I am grateful to you. Thank you so much.
– Vk1
Jun 10 at 15:27
• I just googled some keywords. Jun 10 at 15:48