Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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