So, I've been given this question in my homework and I tried to solve it for a few days, but I can't reach to any solution :(

Given the enhanced Bubble Sort algorithm, the average runtime is:

whereas the array contains only numbers between 1 to n, and all the numbers in the array are different from each other (the "permutation i" in the given formula is a single permutation of the numbers in the array, array indexed from 0 to n-1)

I need to prove that the average runtime in the formula is Big Omega of (n^2), and then conclude that it is also Big Theta of (n^2)

I also know that when the number 1 is in the k position (k is between 0 and n-1), the algorithm performs at lesast n*k operations