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!

The algorithm removes one inversion at a time. In the worst case, it does O(n^2) swaps, and perhaps O(n^3) other operations, since at least half of the swaps will occur at the second half of the array. — Gassa
– Gassa, Commented Apr 10, 2015 at 22:31

templatetypedef · Accepted Answer · 2015-04-10 22:36:46Z

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!

recursive · Accepted Answer · 2015-04-10 22:31:08Z

6

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).

answered Apr 10, 2015 at 22:31

recursive

86.4k36 gold badges155 silver badges246 bronze badges

Comments

Timberwoof · Accepted Answer · 2015-04-10 22:37:57Z

This is one half of the infamous Bubble Sort, which has a O(N^2). This partial sort has O(N) because the For loop goes from 1 to N. After one iteration, you will end up with the largest element at the end of the list and the rest of the list in some changed order. To be a proper Bubble Sort, it needs another loop inside this one to iterate j from 1 to N-i and do the same thing. The If goes inside the inner loop.

Now you have two loops, one inside the other, and they both go from 1 to N (sort of). You will have N * N or N^2 iterations. Thus O(N^2) for the Bubble Sort.

Now you have take your next step as a programmer: Finish writing the Bubble Sort and make it work correctly. Try it with different lengths of list a and see how long it takes. Then never use it again. ;-)

You seem to have overlooked the i = 0;, which resets the loop and makes the algorithm O(n<sup>3</sup>) rather than O(n<sup>2</sup>).

Collectives™ on Stack Overflow

Worst case time complexity for this stupid sort?

3 Answers 3

Comments

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Related