Cuántos operación son necesarios para ordenar una matriz de números.

Question

En StackOverflow, una simple pregunta que me inspiró para crear una ecuación para una respuesta. Pero resulta que, es un poco complicado (en mi humilde opinión) de problemas matemáticos, a saber:

Dado un array de n elementos, es posible que en O(n) tiempo, a la figura cuántas operaciones* será necesario, si se ha de ordenar que matriz de elementos utilizando el algoritmo de ordenación por burbuja ?

*número total de swaps.

Answer 1

Yo no lo creo. Esto es equivalente a calcular el Kendall tau coeficiente. Hay un par de algoritmos para hacer esto (uno de los cuales implica el uso de una Combinación de ordenación para calcular cuántos pasos especie de Burbuja iba a tomar), pero las $O(n\cdot log\ n)$.