An exciting math question asked in Tower Research Capital
Another approach:
As the chances of each swap is independent (and =1/2).
Lets see for the first loop of comparisions, how many swaps are possible:
As there are n numbers, there will be n-1 comparisons, thus average number of swaps coming to be as (n-1)/2.
Similarly in the next loop, we have n-2 comparisons, then n-3, n-4,.. up till 1.
Thus, the total number of comparisons turning out to be sum of first n-1 numbers, i.e. n*(n-1)/2.
And the average number of swaps being the half of it, we get our answer to be n(n-1)/4.
Good one
Another approach:
As the chances of each swap is independent (and =1/2).
Lets see for the first loop of comparisions, how many swaps are possible:
As there are n numbers, there will be n-1 comparisons, thus average number of swaps coming to be as (n-1)/2.
Similarly in the next loop, we have n-2 comparisons, then n-3, n-4,.. up till 1.
Thus, the total number of comparisons turning out to be sum of first n-1 numbers, i.e. n*(n-1)/2.
And the average number of swaps being the half of it, we get our answer to be n(n-1)/4.
Good one