Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?
This was my solution: My aim was to write an algorithm for this and also find the running time.
def Inversion(A):
n = len(A)
for i in range(0,n):
for j in range(i+1, n):
if (A[i] > A[j]):
print(i,j)
Cost on line 1 is $C_1$
Cost on line 2 is $C_2n$ where n is the length of the list
Cost on line 3 is $C_3\sum_{i=1}^{n}{t_i}$ where $t_i = n - i$
Cost on line 4 is $C_4\sum_{i=1}^{n}{t_i - 1}$
Cost on line 5 is $C_5$ (I didn't know how to write it in terms of $n$ and $t_i$
So the total cost will be
$C_1 + C_2n + C_3\sum_{i=1}^{n}{t_i} + C_4\sum_{i=1}^{n}({t_i - 1}) + C_5$
But $\sum_{i=1}^{n}{t_i} = (n - 1) + (n - 2) + (n -3) + (n -4) + (n - 5)....0 = \frac{n(n-1)}{2}$
and $\sum_{i=1}^{n}{t_i - 1} = \frac{n(n-1)}{2} - n $
so our total cost will now be
$C_1 + C_2n + C_3(\frac{n(n-1)}{2}) + C_4(\frac{n(n-1)}{2} - n) + C_5$
which will give us a running time of $\theta(n^2)$
Please am I on the right path ?