Tighter upper bound for sorting permutations with prefix transpositions

Permutations are sequences where each symbol in the given alphabet Σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a prefix transposition. Transpositions over permutations have applications in genome rearrangements and computer interconnection networks. The set of permutations with n   symbols derived from the alphabet Σ={0,1,…,n−1}Σ={0,1,…,n−1} form a symmetric group, that we denote by PnPn. The prefix transposition distance between two permutations π⁎∈Pnπ⁎∈Pn and π∼∈Pnπ∼∈Pn is the minimum number of prefix transpositions, also called moves  , needed to transform π⁎π⁎ into π∼π∼. A prefix transposition can be modeled by a permutation operation. A permutation is type of sequence and it is also an operation. The generators for prefix transposition operation are a subset of permutation operation. As a result, transforming an arbitrary π⁎∈Pnπ⁎∈Pn to an arbitrary π∼∈Pnπ∼∈Pn is equivalent to sorting some πˆ∈Pn. Thus, upper bound for transforming any π⁎∈Pnπ⁎∈Pn into any π∼∈Pnπ∼∈Pn with prefix transpositions is simply the upper bound to sort any permutation π∈Pnπ∈Pn with moves. In the article that establishes the best known upper bound for prefix transposition distance over PnPn as n−log9/2⁡nn−log9/2⁡n, explicit proofs were not given for some cases. In this article, we provide the missing proofs, validating the stated upper bound. Furthermore, we establish an upper bound of n−log7/2⁡nn−log7/2⁡n for prefix transposition distance over PnPn.