# Evaluating the average time complexity of a given bubblesort algorithm.

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.

-
you first need to define what average even means. Since the algorithm is deterministic, you'd have to assume some kind of distribution over inputs. – Suresh Mar 6 '12 at 20:59
@Sim Can you show how you computed the worst-case time complexity? Then, we might get an idea on what you mean by average complexity in your case. – Sunil Mar 6 '12 at 21:04
I mean average-time in the way of the most-likely time needed (or in other words the 'pure' mathematical version of: the mean of all times observed doing a statistical analysis). For example quicksort does have an average of nlogn even though its worst case is n^2. – Sim Mar 6 '12 at 21:07
@Sim In the case of bubble sort average case = worst case time complexity, meaning, Average case Time complexity is also $n^2$ – Sunil Mar 6 '12 at 21:20
There's a difference. quicksort is averaged "over the choice of coin tosses when choosing a pivot" which has nothing to do with the data. Whereas you are implying that you want to average "over all inputs" which assumes (for example) that you expect each ordering of the input to occur with the same probability. that's reasonable, but it should be stated explicitly. – Suresh Mar 6 '12 at 21:21

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.

-
If you consider a normal distribution, is there a way to approximate $c_d$ ? – Sim Mar 6 '12 at 21:48
You can say $c_d≥(n+1-d)(d-1)!$ because you can mingle anywhere all the permutations of [$2$, .., $d$] and append $1$ at the end but that's to small to prove $n²$ in average. – jmad Mar 6 '12 at 22:15

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}$$

-
this evaluates the amount of inversions. but how about the amount of comparisons which depends on the time the break-clause is stepped in – Sim Mar 6 '12 at 22:20
You get one comparison by swap and most importantly one swap can reduce the number of inversions by at most one. – jmad Mar 6 '12 at 22:24
not every comparison results in a swap, if the if-clause is false, no inversion is done. – Sim Mar 6 '12 at 22:31
@rgrig If you provide a counter-example, then I will correct my answer. – Joe Mar 7 '12 at 0:18
@Joe: I removed my comment. It was wrong. – rgrig Mar 7 '12 at 7:06

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)

-