2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Feb 8, 2017 at 4:02
  • $\begingroup$ @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 $\endgroup$
    – Vk1
    Feb 8, 2017 at 4:09
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Feb 8, 2017 at 4:22
  • $\begingroup$ @D.W. :- I have made the changes, and given an example in the description. I hope this clarifies everything. $\endgroup$
    – Vk1
    Feb 8, 2017 at 13:16

1 Answer 1

Reset to default
2
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Vk1
    Jun 10, 2022 at 15:27
  • $\begingroup$ I just googled some keywords. $\endgroup$
    – Yuval Filmus
    Jun 10, 2022 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.