# 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

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)$.