# How many operation are required to sort a array of numbers.

On StackOverflow, a simple question inspired me to create an equation for a answer. But it turn out that, it is kind of complicated (IMHO) mathematical problem, namely:

Given an array of n elements, is it possible in O(n) time, to figure out how many operations* will be required, if we were to sort that array of elements using bubble sort algorithm ?

*total number of swaps.

• By operations, I presume you mean number of swaps? Interesting question. – Aryabhata Feb 2 '12 at 23:24
• @Aryabhata, yes. I will update my question with that – Damian Leszczyński - Vash Feb 2 '12 at 23:40

## 1 Answer

I don't believe so. This is equivalent to computing the Kendall tau coefficient. There are a couple algorithms for doing this (one of which involves using a Merge sort to compute how many steps Bubble sort would take) but they are $O(n\cdot log\ n)$.

• Now I also believe is not possible. Thank you for your time. – Damian Leszczyński - Vash Feb 3 '12 at 0:56