Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm (Q2628258)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm
scientific article

    Statements

    Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm (English)
    0 references
    0 references
    0 references
    13 June 2017
    0 references
    Summary: The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and Müller.
    0 references
    Novelli-Pak-Stoyanovskii algorithm
    0 references
    standard Young tableau
    0 references
    hook-length formula
    0 references
    average case and worst case complexity
    0 references
    symbolic summation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references