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 lower 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

$\endgroup$
  • $\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 '17 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 '17 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 '17 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 '17 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.