Evaluating the average time complexity of a given bubblesort algorithm.

Question

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.

Answer 1

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'

Answer 2

Recall that a pair $(A[i], A[j])$ (resp. $(i,j)$) is inverted if $i < j$ and $A[i] > A[j]$.

Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.

Calculating the expected number of inversions in a uniform random permutation is easy:

Let $P$ be a permutation, and let $R(P)$ be the reverse of $P$. For example, if $P = 2,1,3,4$ then $R(P) = 4,3,1,2$.

For each pair of indices $(i,j)$ there is an inversion in exactly one of either $P$ or $R(P)$.

Since the total number of pairs is $n(n-1)/2$, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:

$$\frac{n(n-1)}{4}$$

Answer 3

Number of swaps < Number of iterations (in both optimized as well as simple bubble case scenario)

Number of Inversions = Number of swaps.

Therefore, Number of Iterations > $\frac{n(n-1)}{4}$

Thus, Average case complexity is $\omega(n^2)$. But, since average case cant exceed worst case, we get that it is $O(n^2)$,

This gives us : Average Time = $\theta(n^2)$

(Time complexity = Number of iteration no. of iterations > no. of swaps)

Answer 4

in this document, the average time complexity of bubble sort reached O(nlog(n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf