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
            switched := true
    IF switched = false THEN

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.

  • 6
    $\begingroup$ 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. $\endgroup$
    – Suresh
    Commented Mar 6, 2012 at 20:59
  • $\begingroup$ @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. $\endgroup$
    – 0x0
    Commented Mar 6, 2012 at 21:04
  • $\begingroup$ 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. $\endgroup$
    – Sim
    Commented Mar 6, 2012 at 21:07
  • 1
    $\begingroup$ @Sim In the case of bubble sort average case = worst case time complexity, meaning, Average case Time complexity is also $n^2$ $\endgroup$
    – 0x0
    Commented Mar 6, 2012 at 21:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – Suresh
    Commented Mar 6, 2012 at 21:21

4 Answers 4


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'

  • $\begingroup$ If you consider a normal distribution, is there a way to approximate $c_d$ ? $\endgroup$
    – Sim
    Commented Mar 6, 2012 at 21:48
  • $\begingroup$ 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. $\endgroup$
    – jmad
    Commented Mar 6, 2012 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:


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


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

  • 1
    $\begingroup$ That's not true. They prove a result of Knuth showing that the expected number of comparisons is roughly $n^2/2$. $\endgroup$ Commented Feb 19, 2018 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.