Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 –  Vash - Damian Leszczyński Feb 2 '12 at 23:40

1 Answer 1

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|improve this answer
1  
Now I also believe is not possible. Thank you for your time. –  Vash - Damian Leszczyński Feb 3 '12 at 0:56

Your Answer

 
discard

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.