A complexity theorem for the Novelli–Pak–Stoyanovskii algorithm

We describe two aspects of the behaviour of entries of Young tableaux during the application of the Novelli–Pak–Stoyanovskii algorithm. We derive two theorems which both imply a generalised version of a conjecture by Krattenthaler and Müller concerning the complexity of the Novelli–Pak–Stoyanovskii algorithm.