Worst case time complexity for this stupid sort?

Question

The code looks like:

for (int i = 1; i < N; i++) {
    if (a[i] < a[i-1]) {
        swap(i, i-1);
        i = 0;
    }
}

After trying out a few things i figure the worst case is when the input array is in descending order. Then looks like the compares will be maximum and hence we will consider only compares. Then it seems it would be a sum of sums, i.e sum of ... {1+2+3+...+(n-1)}+{1+2+3+...+(n-2)}+{1+2+3+...+(n-3)}+ .... + 1 if so what would be O(n) ?

If I am not on the right path can someone point out what O(n) would be and how can it be derived? cheers!

Answer 1

For starters, the summation

(1 + 2 + 3 + ... + n) + (1 + 2 + 3 + ... + n - 1) + ... + 1

is not actually O(n). Instead, it's O(n³). You can see this because the sum 1 + 2 + ... + n = O(n², and there are n copies of each of them. You can more properly show that this summation is Θ(n³) by looking at the first n / 2 of these terms. Each of those terms is at least 1 + 2 + 3 + ... + n / 2 = Θ(n²), so there are n / 2 copies of something that's Θ(n²), giving a tight bound of Θ(n³).

We can upper-bound the total runtime of this algorithm at O(n³) by noting that every swap decreases the number of inversions in the array by one (an inversion is a pair of elements out of place). There can be at most O(n²) inversions in an array and a sorted array has no inversions in it (do you see why?), so there are at most O(n²) passes over the array and each takes at most O(n) work. That collectively gives a bound of O(n³).

Therefore, the Θ(n³) worst-case runtime you've identified is asymptotically tight, so the algorithm runs in time O(n³) and has worst-case runtime Θ(n³).

Hope this helps!

Answer 2

It does one iteration of the list per swap. The maximum number of swaps necessary is O(n * n) for a reversed list. Doing each iteration is O(n).

Therefore the algorithm is O(n * n * n).