6
$\begingroup$

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.

  • 0
    @Aryabhata, yes. I will update my question with that2012-02-02

1 Answers 1

3

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

  • 1
    Now I also believe is not possible. Thank you for your time.2012-02-03