Evaluating the average time complexity of a given bubblesort algorithm.
Recall that a pair $(A[i], A[j])$ (resp. $(i,j)$) is inverted if $i &lt; j$ and $A[i] &gt; 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}$$