Evaluating the average time complexity of a given bubblesort algorithm.

ignougroup
Question Detail: Considering this pseudo-code of a bubblesort: 

FOR i := 0 TO arraylength(list) STEP 1       switched := false     FOR j := 0 TO arraylength(list)-(i+1) STEP 1         IF list[j] > list[j + 1] THEN             switch(list,j,j+1)             switched := true         ENDIF     NEXT     IF switched = false THEN         break     ENDIF NEXT

What would be the basic ideas I would have to keep in mind to evaluate the average time-complexity? I already accomplished calculating the worst and best cases, but I am stuck deliberating how to evaluate the average complexity of the inner loop, to form the equation. The worst case equation is: $$ sum_{i=0}^n left(sum_{j=0}^{n -(i+1)}O(1) + O(1)right) = O(frac{n^2}{2} + frac{n}{2}) = O(n^2) $$ in which the inner sigma represents the inner loop, and the outer sigma represents the outer loop. I think that I need to change both sigmas due to the “if-then-break”-clause, which might affect the outer sigma but also due to the if-clause in the inner loop, which will affect the actions done during a loop (4 actions + 1 comparison if true, else just 1 comparison). For clarification on the term average-time: This sorting algorithm will need different time on different lists (of the same length), as the algorithm might need more or less steps through/within the loops until the list is completely in order. I try to find a mathematical (non statistical way) of evaluating the average of those rounds needed. For this I expect any order to be of the same possibility.

Asked By : Sim
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20

Answered By : jmad

For lists of length $n$, average usually means that you have to start with a uniform distribution on all $n!$ permutations of [$1$, .., $n$]: that will be all the lists you have to consider. Your average complexity would then be the sum of the number of step for all lists divided by $n!$. For a given list $(x_i)_i$, the number of steps of your algorithm is $nd$ where $d$ is the greatest distance between a element $x_i$ and his rightful location $i$ (but only if it has to move to the left), that is $max_i(max(1,i-x_i))$. Then you do the math: for each $d$ find the number $c_d$ of lists with this particular maximal distance, then the expected value of $d$ is: $$frac1{n!} sum_{d=0}^n{ dc_d}$$ And that’s the basic thoughts without the hardest part which is finding $c_d$. Maybe there is a simpler solution though. EDIT: added `expected’