Complexity of a maximum algortihm

Question

I have a basic maximum algorithm like this:

for(int i = 1; i < a.length; i++){
    if(a[i-1]>a[i]){
        // Switch a[i-1] with a[i]
        int temp = a[i-1]; a[i-1] = a[i]; a[i] = temp;
    }
}

And the task is to find the average number of times the switch happens. The answer should be log(n), but I don’t understand how.

So with the best case, it happens 0 times (if the array is already sorted), and the worst case it happens (n-1) times (if it is sorted decreasingly).

I tried to make random permutation of n numbers and find the average, but I find that the number of switches on average is almost starting to creep to about n. What is the explanation for this complexity? I have racked my brain about this too long.

Answer 1

The claim that the average number of times the swap happens would be log𝑛 is false. However, if we would count the average number of times the swap doesn't happen, it ends up as O(log𝑛).

Proof

Let's assume the array has length 𝑛, and has distinct integer values between 0 and 𝑛−1 (included).

The maximum number of swaps is 𝑛−1.

The probability of not having a swap in the first iteration is 1/2

For the second iteration we can reason as follows:

The distribution of the first two values is assumed to be an even distribution and so the expected lowest value is ~(1/3)𝑛 and the expected greatest value is ~(2/3)𝑛. As after the first iteration that greatest value must sit at index 1, we have an expected probability of 1/3 of not swapping with the next value in the array.

Similarly for the third iteration we can say there is a 1/4 probability of not swapping...

And so it continues until the last iteration, where we will have at index i-1 either the greatest value (greatest probability) or a tiny probability that the greatest value sits already at index i. The number of cases where the latter is the case is 1/𝑛^th of the total number of cases.

Therefore the expected total number of non-swaps is a series with 𝑛−1 terms:

      1/2 + 1/3 + ... + 1/𝑛

If we would prefix this with an extra term 1/1, then this is the harmonic series that asymptotically approaches log𝑛. For asymptotic complexity the missing term 1 is not relevant.

So we can conclude that the number of times there is no(!) swap, has a complexity of O(log𝑛). The number of swaps has a complexity of O(𝑛−1−log𝑛) which is O(𝑛).