Evaluating the average time complexity of a given bubblesort algorithm.

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'