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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.