# Minimum number of transpositions

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \sim n^2$ but I cannot find a formal proof.

• So you are doing something like sorting and counting minimal swaps possible? And it seems quite $O(n)$ to me if I understood your intentions.
– Evil
Jul 21, 2016 at 18:21
• Hint: how many inversions can a single swap reverse at best?
– Raphael
Jul 21, 2016 at 21:39
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jul 21, 2016 at 21:39
• Single swap allows only one reversion. BTW I haven't found how to edit titles. Jul 23, 2016 at 7:05

If your transpositions form a permutation $\pi$ then (using the appropriate convention for multiplication) $A\pi = B$ and so $\pi = A^{-1} B$. This shows that we can assume without loss of generality that $A$ is the identity, and the question now becomes: how many transpositions do we need to multiply in the worst case to get any particular permutation? This might be a question you already know how to answer.